快速排序(Quicksort)是對冒泡排序的一種改進。由C. A. R. Hoare在1962年提出。在平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他Ο(n log n) 算法更快，因為它的內部循環(inner loop)可以在大部分的架構上很有效率地被實現出來。

快速排序使用分治法(Divide and conquer)策略來把一個串行(list)分為兩個子串行(sub-lists)。

算法步驟：

1 從數列中挑出一個元素，稱為 “基準”(pivot)，

2 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面(相同的數可以到任一邊)。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區(partition)操作。

3 遞歸地(recursive)把小于基準值元素的子數列和大于基準值元素的子數列排序。

遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的迭代(iteration)中，它至少會把一個元素擺到它最后的位置去。

快速排序算法，具體代碼如下：package?com.yoodb;

/**

*?快速排序法

*?@author?www.yoodb.com

*/

public?class?QuickSort?{

public?static?void?main(String[]?args)?{

int?[]n?=?{30,3,35,19,44,12};

quickSort(n,0,?n.length?-1);

for?(int?i?=?0;?i?

System.out.println(n[i]);

}

}

public?static?void?quickSort(int[]?n,int?left,int?right){

int?pivot;

if(left?

pivot?=?partition(n,?left,?right);

quickSort(n,?left,?pivot?-?1);

quickSort(n,?pivot?+?1,?right);

}

}

//?分治法

private?static?int?partition(int[]?n,int?left,int?right){

int?pivot?=?n[left];

while(left?

while(left?=?pivot)?right--;

if(left?

n[left++]?=?n[right];

while(left?

if(left?

n[right--]?=?n[left];

}

n[left]?=?pivot;

return?left;

}

/*private?static?int?partition(int[]?n,int?left,int?right){

int?pivot?=?n[left];

while(left?

while(left?=?pivot)?right--;

n[left]?=?n[right];

while(left?

n[right]?=?n[left];

}

n[left]?=?pivot;

return?left;

}*/

}

總結

以上是生活随笔為你收集整理的oracle快速排序法,经典算法系列之快速排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。