正文之前
快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort）亡蓉，一種排序算法晕翠，最早由東尼 * 霍爾提出。在平均狀況下砍濒，排序n個(gè)項(xiàng)目要O(nlogn)次比較淋肾，在最壞情況下則需要O(n2)次比較，但這種狀況并不常見爸邢。事實(shí)上樊卓，快速排序通常明顯比其他O(nlogn)算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來杠河。??????????????——Wikipedia
本文將介紹以下內(nèi)容
排序原理
算法實(shí)現(xiàn)（JAVA）
測試階段
算法分析
正文
排序原理
和歸并排序劃清界限：
歸并排序：將一個(gè)數(shù)組分成兩個(gè)字?jǐn)?shù)組碌尔，分別排序兩部分，將有序的子數(shù)組歸并得到整個(gè)有序數(shù)組
快速排序：將一個(gè)數(shù)組分成兩個(gè)字?jǐn)?shù)組券敌，分別排序兩部分唾戚，當(dāng)兩個(gè)子數(shù)組有序時(shí)，整個(gè)數(shù)組自然就有序了
快速排序使用一個(gè)切分元素來劃分?jǐn)?shù)組待诅，切分元素左邊的數(shù)組元素小于切分元素叹坦，右邊的數(shù)組元素大于于切分元素，所以兩個(gè)子數(shù)組有序就會(huì)得到整個(gè)有序的數(shù)組
算法實(shí)現(xiàn)
1. 切分?jǐn)?shù)組
private static int partition(int[] a, int low, int high){
int i = low, j = high + 1; //由兩邊向中間掃描
int p = a[low]; //切分?jǐn)?shù)組的元素
while(true){
while(a[++i] < p){ // i 的值會(huì)一直遞增至 a[++i] >= p
if(i == high){ //掃描結(jié)束
break;
}
}
while(a[--j] > p){ // j 的值會(huì)一直遞減至 a[++i] >= p
if(j == low){ //掃描結(jié)束
break;
}
}
if(i >= j){ // j 的位置就是切分元素在有序數(shù)組中的位置
break;
}
int temp = a[i]; //交換元素順序
a[i] = a[j];
a[j] = temp;
}
int temp = a[low]; //將切分元素交換至中間位置
a[low] = a[j];
a[j] = temp;
return j;
}
2. 數(shù)組排序
這一部分的代碼和歸并排序的排序代碼相似
private static void quickSort(int[] a){
sort(a, 0, a.length - 1);
}
private static void sort(int[] a, int lo, int hi){
if(hi <= lo){
return ;
}
int j = partition(a, lo, hi);
sort(a, lo, j - 1);
sort(a, j + 1, hi);
}
sort方法遞歸調(diào)用自己咱士，將數(shù)組劃分至最小立由，每次都將子序列中的第一個(gè)元素作為切分元素轧钓，來將數(shù)組排序
整個(gè)排序過程的代碼：
public class QuickSort {
private static int partition(int[] a, int low, int high){
int i = low, j = high + 1; //由兩邊向中間掃描
int p = a[low]; //切分?jǐn)?shù)組的元素
while(true){
while(a[++i] < p){ // i 的值會(huì)一直遞增至 a[++i] >= p
if(i == high){ //掃描結(jié)束
break;
}
}
while(a[--j] > p){ // j 的值會(huì)一直遞減至 a[++i] >= p
if(j == low){ //掃描結(jié)束
break;
}
}
if(i >= j){ // j 的位置就是切分元素在有序數(shù)組中的位置
break;
}
int temp = a[i]; //交換元素順序
a[i] = a[j];
a[j] = temp;
}
int temp = a[low]; //將切分元素交換至中間位置
a[low] = a[j];
a[j] = temp;
return j;
}
private static void quickSort(int[] a){
sort(a, 0, a.length - 1);
}
private static void sort(int[] a, int lo, int hi){
if(hi <= lo){
return ;
}
int j = partition(a, lo, hi);
sort(a, lo, j - 1);
sort(a, j + 1, hi);
}
}
測試階段
public static void main(String[] args){
int[] a = new int[10];
for (int i = 0; i < 10; i++) {
a[i] = (int)(Math.random() * 100);
System.out.print(a[i] + " ");
}
quickSort(a);
System.out.println();
for (int i = 0; i < 10; i++) {
System.out.print(a[i] + " ");
}
}
生成10個(gè)隨機(jī)數(shù)字并調(diào)用快速排序方法序厉，最后輸出結(jié)果：
算法分析
1. 特點(diǎn)
快速排序?qū)崿F(xiàn)簡單，應(yīng)用廣泛毕箍，比一般算法要快很多弛房，并且是原地排序（借助輔助棧）
2. 時(shí)間復(fù)雜度
設(shè)數(shù)組的長度為N，用 T(N) 表示排序一個(gè)長度為N的數(shù)組所需要的比較次數(shù)而柑，可想而知文捶，T(0) 和 T(1) 為0
切分的成本為N + 1，左子數(shù)組排序的平均成本為(C1 + C2 + ... + CN - 2 + CN - 1)/N媒咳，右子數(shù)組排序的平均成本為(CN - 1 + CN - 2 + ... + C2 + CN)/N
CN = N + 1 + (C1 + C2 + ... + CN - 2 + CN - 1)/N + (CN - 1 + CN - 2 + ... + C2 + CN)/N
經(jīng)過化簡之后得到：CN ~ 2(N + 1)(1/3 + 1/4 + ... + 1/(N + 1))
積分得到CN ~ 2NlogN
所以粹排，算法復(fù)雜度為 O(nlogn)
3. 穩(wěn)定性
舉個(gè)例子，一個(gè)數(shù)組a = [6,4,3,2,3,7,8,7,9]涩澡，a[0]和a[4]交換顽耳，第二個(gè) 3 就移動(dòng)到了第一個(gè) 3 的前面，所以是不穩(wěn)定的，不穩(wěn)定性體現(xiàn)在切分元素交換的時(shí)候
關(guān)于快速排序的介紹就到這里了射富，謝謝膝迎！
