你真的完全理解了快速排序嗎？如果沒有請仔細閱讀本文褥琐，讓我們一起成長。廢話不哆嗦炭臭，開始今天的學習——快速排序永脓，單獨說明快速排序是因為其重要，首先快速排序是基礎排序算法中表現比較亮眼的鞋仍，其次是因為快排還有很多的改進方式常摧，具體介紹如下。
快速排序基礎
快速排序的思想是采用分治的算法思想威创，具體算法是選擇一個隨機元素落午，通常是待排數組的起點，然后設置前后指針肚豺，對比確定該元素的位置溃斋，并且在確定位置的過程中進行數據交換，讓確定元素位置的之前的元素都小于選擇的元素吸申，讓后面的元素都大于該元素梗劫，那么這個元素的位置在整個數組中就是確定；然后以此類推截碴，在數組前半部分循環(huán)上面步驟梳侨，在數組后半部分循環(huán)使其有序，直到分到一個元素時日丹，即得到一個序列有序走哺。具體代碼如下：
public static void sort(int[] nums, int low, int high){
Array.nonEmpty(nums);
if(low < high){
int mid = partition(nums, low, high);
sort(nums, low, mid-1);
sort(nums, mid+1, high);
}
}
public static int partition(int[] nums, int low, int high){
int temp = nums[low];
while(low < high){
while (low < high && nums[high] >= temp) high--;
nums[low] = nums[high];
while (low < high && nums[low] < temp) low++;
nums[high] = nums[low];
}
nums[low] = temp;
return low;
}
快速排序是不穩(wěn)定的排序，不穩(wěn)定的原因就是元素的跨節(jié)點的交換哲虾，如果是相鄰交換丙躏，則是穩(wěn)定排序，快速排序的平均時間復雜度為O(nlgn)束凑，最壞時間復雜度為O(n^2)彼哼，但由于其出現最壞的情況較少，所以其排序性能在排序算法中算好的湘今。
改進一
考慮一下這種情況敢朱，數組有序，然后應用快速排序對數組排序摩瞎，按照上面的實現拴签，選擇最小的元素為隨機元素，那么這時的快排就變成了O(n^2)旗们，所以改進思路就是讓隨機元素變“隨機”蚓哩，改進的第一種思路產生了。下面只給出修改的代碼：
public static int partition(int[] nums, int low, int high){
// 讓隨機元素變的隨機
swap(arr[low], arr[rand() % (high - low + 1) + low]);
int temp = nums[low];
while(low < high){
while (low < high && nums[high] >= temp) high--;
nums[low] = nums[high];
while (low < high && nums[low] < temp) low++;
nums[high] = nums[low];
}
nums[low] = temp;
return low;
}
這種改進方式對已經有序的數組是有效的上渴，能夠降低其時間復雜度岸梨。
改進二
試想這樣一種情況喜颁，排序數組中存在大量的重復元素，那么在分治的過程中曹阔，相同元素會分布在同一個分區(qū)中半开，如果重復元素比較多，會造成分區(qū)的長度極不平衡赃份，增加排序的復雜度寂拆。基于此我們可以提出兩種改進方式抓韩，其中一種是將重復的元素均勻的分部在兩個分區(qū)中纠永，這樣解決了大于、小于兩個分區(qū)長度不平衡的問題谒拴，這種改進方式為雙路快排尝江，代碼實現如下：
private static int partition(int[] nums, int start, int end) { // 排序方法和普通快排相同
int i = start + 1;
int j = end;
int v = nums[start];
while (true) {
while (i <= end && nums[i] < v) i++;
while (j >= start + 1 && nums[j] > v) j++; // 沒有等號，否則從這就直接走了
if (i > j) break;
swap(nums, i, j);
i++;
j--;
}
swap(nums, start, j);
return j;
}
大量重復元素進行排序時英上，普通快排由于遞歸層數較大炭序，很快就是棧溢出，但是在百萬級重復元素的情況下善延，雙路快排還是能夠快速將數據排好少态，很強悍城侧！但是易遣，這種方式雖然讓分區(qū)平衡，但是其沒有解決相同元素比較的問題嫌佑，所以這就是產生了下一種優(yōu)化的方式豆茫，three-way QS（三路快排），其改進思想是屋摇，在原來大于揩魂、小于兩個分區(qū)的基礎上增加一個等于的分區(qū)，將原來的兩個分區(qū)炮温，擴充至三個分區(qū)火脉，這樣等于的分區(qū)中元素就可以不參與排序，而直接排好大于和小于兩個分區(qū)的元素即可柒啤，具體代碼實現如下：
private static void sort(int[] array, int start, int end) {
Arrays.nonEmpty(array);
if (start > end) return;
//找到一個隨機key
int value = array[start];
int lt = start; int gt = end + 1; int i = start + 1;
while (i < gt) {
if (array[i] < value) {
swap(array, i, lt + 1);
lt++; i++;
} else if (array[i] > value) {
swap(array, i, gt - 1);
gt--;
} else i++;
}
swap(array, lt, start);
//直接跳過相等元素的比較
sort(array, start, lt - 1);
sort(array, gt, end);
三路快排很好的解決了數據重復的問題倦挂，能夠在數據大量重復的情況下，提升排序性能（這里就不給出性能對比了）担巩；
改進三
在快排算法中還有一種改進方式方援，即內省式快排，在STL中的快排使用的就是這種算法涛癌。首先看一下這種改進方式針對的問題以及改進的思路犯戏。
1.為什么需要這種算法
快排在排序小數組（比如大小為10的數組）且基本有序的情況下送火，它的表現還沒插入排序要好（很多改進是在分區(qū)起止位置小于一定長度后改用插入排序）。因為數組是基本有序先匪，使得插入排序不用很多次的執(zhí)行元素的移動种吸，并且可以避免遞歸。 在SGI STL中的函數sort使用的排序算法就是內省式的排序算法胚鸯。內省的排序算法是基于快排實現的衣屏。假設待排序的數組大小為n洞拨，去一個k值，使得k為滿足2^k <= n的最大值。k為最大的遞歸層次哈扮、 為什么要設置最大遞歸層次呢？ 因為快排的遞歸層次過深的時候岁钓，很可能會退化成O(n^2)狸捅。內省式排序使用k來控制快排的遞歸深度，當快排的遞歸深度到達k的時候選擇使用heap排序拟糕。
2. 為什么不一開始就使用heap排序
heap排序在平均時間復雜度是O(nlgn)判呕，最壞情況也是O(nlgn)，看起來要比快排要快送滞。但是實際上侠草，快排是要比heap排序要快，第一個原因是：heap排序雖然和快排在平均情況下的時間復雜度是O(nlgn)犁嗅，但是heap排序的時間常數要比快排的時間常數要大边涕。第二個原因是：據統(tǒng)計，快排的最壞情況在是很少發(fā)生的褂微。第三個原因是：快排能夠比較好的吻合程序的空間局部性原理功蜓，因為它操作的基本都是相鄰的元素（虛擬存儲器的設計理論基礎中就有程序的時間局部性和空間局部性），能夠減少內存缺頁中斷的發(fā)生次數宠蚂。
3.為什么要使用heap排序呢
因為在遞歸層次太深的時候式撼，就意味著發(fā)生最壞情況的概率大大的提升了，這時候因為heap排序的最壞情況下的時間復雜度是O(nlgn)比快排的O(n^2)要好求厕，因此使用heap排序能更好優(yōu)化排序效率著隆。
基于以上三點，誕生了一種新的改機算法呀癣，即內省排序美浦，名字很符合算法思想，自我省查十艾，發(fā)現苗頭不對抵代，立即采用候補排序算法，不是一條道走到黑忘嫉，算法領域的思想和人生是多么相似荤牍，只有這樣才能獲得很好的性能表現案腺；這個算法就不給出具體實現了，主要是有點復雜康吵，但是這種改進算法的思路值得我們思考借鑒劈榨，
總結
本文主要是介紹了快速排序及其幾種改進思路，要改進一種算法必須是建立在對其十分了解并且充分思考過后的晦嵌，學習算法思想是一方面同辣，但對于大多數人來說，算法高效實現才是比較考驗人的惭载，好多人都是知道其思想旱函，但是實現不了，讀萬卷書描滔，還要行萬里路棒妨，在編程領域，后者更為重要含长，完畢券腔。
紙上得來終覺淺，絕知此事要躬行拘泞。 ——陸游
