快速排序
原理： 快速排序使用分治法（Divide and conquer）策略來把一個序列分為較小和較大的2個子序列扯饶，然后遞歸地排序兩個子序列。
步驟為：
1.挑選基準值：從數(shù)列中挑出一個元素舒憾，稱為“基準”（pivot）控轿；
2.分割：重新排序數(shù)列叶雹，所有比基準值小的元素擺放在基準前面解阅，所有比基準值大的元素擺在基準后面（與基準值相等的數(shù)可以到任何一邊）回梧。在這個分割結束之后，對基準值的排序就已經(jīng)完成祖搓；
3.遞歸排序子序列：遞歸地將小于基準值元素的子序列和大于基準值元素的子序列排序狱意。
遞歸到最底部的判斷條件是數(shù)列的大小是零或一，此時該數(shù)列顯然已經(jīng)有序拯欧。
選取基準值有數(shù)種具體方法详囤，此選取方法對排序的時間性能有決定性影響。因此快速排序屬于不穩(wěn)定排序镐作。
對基準值選擇對排序帶來的影響藏姐，大家可以參考我自己寫的一套OC代碼實現(xiàn)，這個Demo中對比了三大基本排序和快速排序的效率该贾，快速排序也支持選取第一個或最后一個或中間位為基準值羔杨。同學們可以手動設置數(shù)據(jù)源，對比一下這幾種排序的效率杨蛋，也可以觀察不同基準值的快速排序效率上的差異兜材。
快速排序的實現(xiàn)代碼：
在前面我們知道，選取正確的基準值對排序的性能有著決定性的影響逞力，在這里我們選擇序列中間的值作為基準值曙寡。
代碼主要分為兩個部分：進行切分的代碼和進行遞歸調(diào)用的代碼
第一部分 進行切分
/**
* 進行切分，并進行交換
* @param a 數(shù)組
* @param lo 切分開始的位置
* @param h 切分結束的位置
* @return 返回分界點的位置
*/
public static int partition(int[] a,int lo,int h){
// 選取中間的值為基準值
int middle = (lo+h+1)/2;
int v = a[middle];
// 將基準值和a[lo]交換位置
exc(a, lo, middle);
int i = lo;
int j = h+1;
while(true){
// 假如左邊的小于基準值寇荧，則一直進行循環(huán)
while(a[++i] < v){
// 防止越界
if(i == h){
break;
}
}
// 假如右邊的大于基準值举庶，則一直進行循環(huán)
while(a[--j]>v){
if(j == lo){
break;
}
}
// 一旦i>=j則代表i前面的除第一個外都比基準值小，j后面的都比基準值大揩抡，這時候就可以跳出循環(huán)了
if(i>=j){
break;
}
// 進行交換(因為a[lo]>v,a[h]<v户侥，所以將兩者進行交換)
exc(a, i,j);
}
// 將基準放到分界點
exc(a, lo, j);
return j;
}
第二部分 進行遞歸調(diào)用
/**
* 調(diào)用quickSort函數(shù)
* @param a 數(shù)組
*/
public static void quickSort(int[] a){
quickSort(a,0,a.length-1);
}
/**
* 進行遞歸的快排
* @param a
* @param lo
* @param h
*/
public static void quickSort(int[] a,int lo,int h){
if(h <= lo) {
return ;
}
// j為基準值的位置
int j = partition(a, lo, h);
// 進行遞歸調(diào)用，將j前面的進行快排
quickSort(a,lo,j-1);
// 進行遞歸調(diào)用峦嗤，將j后面的進行快排
quickSort(a,j+1,h);
}
快速排序
特點：
快速排序在最壞的情況下時間復雜度是O(n**2),平均時間復雜度是O(nlogn)蕊唐。快速排序基本上被認為是相同數(shù)量級的所有排序算法中寻仗，平均性能最好的刃泌。
出處：https://www.cnblogs.com/xiaohuiduan/p/11188304.html
GitHub代碼為原創(chuàng)
