基本思想
通過一輪的排序?qū)⑿蛄蟹指畛瑟毩⒌膬刹糠痔笨穑渲幸徊糠中蛄械年P(guān)鍵字（這里主要用值來表示）均比另一部分關(guān)鍵字小矩桂。繼續(xù)對長度較短的序列進行同樣的分割软族，最后到達整體有序添谊。在排序過程中财喳，由于已經(jīng)分開的兩部分的元素不需要進行比較，故減少了比較次數(shù)斩狱，降低了排序時間耳高。
一次劃分基本步驟
- 一個基準(zhǔn)值（通常是第一個數(shù)），兩個指針（前指針i所踊，后指針j）泌枪，起始時前指針指向第一個數(shù)，后指針指向最后一個數(shù)秕岛。
- 后指針從后往前掃描碌燕，遇到比基準(zhǔn)值小的數(shù)a[j]，a[i]與a[j]交換继薛，前指針i+1（為下一步從前往后掃描做準(zhǔn)備）
- 前指針從前往后掃描修壕，遇到比基準(zhǔn)值大的數(shù)a[i]，a[j]與a[i]交換遏考，后指針j+1（為下一步從后往前掃描做準(zhǔn)備）
- 重復(fù)步驟二慈鸠，直到 i == j，則 a[i] = a[j] = 基準(zhǔn)值灌具，且基準(zhǔn)值左邊的數(shù)都比基準(zhǔn)值小青团，基準(zhǔn)值右邊的數(shù)都比基準(zhǔn)值大
算法實現(xiàn)
public int[] sort(int[] a, int left, int right){
if (left < right){//遞歸出口譬巫，left=right說明一組只有一個元素
int i = left;
int j = right;
int temp = a[left];
while (i < j){//一次劃分，i=j說明指針相遇督笆，指針?biāo)冈刈筮吘萢[i]小芦昔，右邊均比a[i]大
while (i < j && a[j] >= temp) {j--;}//后指針向前掃描找到比基準(zhǔn)值小的元素
if(i < j) { a[i++] = a[j];}//若i < j則說明找到，交換
while (i < j && a[i] <= temp) {i++;}
if(i < j) { a[j--] = a[i];}
}
a[i] = temp;
sort(a, left, i - 1);
sort(a, i + 1, right);
}
return a;
}
時間復(fù)雜度
- 最好情況：O(nlogn)
- 最壞情況：每次劃分只比上一次少了一個元素娃肿，也就是每次劃分都只拿到了最大或最小的元素烟零，退化為冒泡排序，n*n
- 一般情況：O(nlogn)
證明：快速排序時間復(fù)雜度為O（n×log（n））的證明
算法改進
- 基準(zhǔn)值的選擇方面咸作。
1锨阿、選取隨機數(shù)作為樞軸。
但是隨機數(shù)的生成本身是一種代價记罚，根本減少不了算法其余部分的平均運行時間墅诡。
2、 使用左端桐智，右端和中心的中值做為樞軸元末早。
經(jīng)驗得知，選取左端说庭，右端然磷，中心元素的中值會減少了快排大約 14%的比較。
3刊驴、每次選取數(shù)據(jù)集中的中位數(shù)做樞軸姿搜。
選取中位數(shù)的可以在 O(n)時間內(nèi)完成。（證明見《算法導(dǎo)論（第二版） 》） P111 第九章中位數(shù) - 快速排序在處理小規(guī)模數(shù)據(jù)時的表現(xiàn)不好捆憎。
這個時候可以改用插入排序舅柜。
當(dāng)數(shù)據(jù)規(guī)模小于一定程度時，改用插入排序躲惰。具體小到何種規(guī)模時致份，采用插入排序，這個理論上還不解础拨，一些文章中說是 5 到 25 之間氮块。SGI STL 中的快速排序采用的值是 10。
