前言
快速排序（Quicksort）是對冒泡排序的一種改進俄占。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數(shù)據(jù)分割成獨立的兩部分画饥，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小袜腥，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序郊霎，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列移袍。
值得注意的是解藻，快速排序算法，是一種不穩(wěn)定的排序算法葡盗，也就是說舆逃，多個相同的值的相對位置也許會在算法結束時產生變動。
快速排序的時間復雜度最低為nlogn，最高為n的平方路狮，它的主要原理是先確定一個基準數(shù)虫啥，這個基準數(shù)可以為做左邊的數(shù)或者最右邊的數(shù)或者隨機數(shù)等等。然后將所有比它小的數(shù)都放到它前面奄妨，所有比它大的數(shù)都放到它后面涂籽。
流程說明
在此舉個例子：
1.首先拿最右邊的這個數(shù)為基準數(shù)。
2.然后用拿最左邊的數(shù)和這個基準數(shù)做比較砸抛，小于這個基準數(shù)评雌，左邊的序號+1，再和這個值進行比較直焙，直到大于這個數(shù)景东，然后基準數(shù)和這個值的位置調換。
3.之后對右邊的數(shù)重復上述的過程奔誓，直到找到一個右邊的數(shù)要小于這個基準數(shù)斤吐，再和這個基準數(shù)進行位置調換，左邊的序號+1厨喂；和措。
4.上述過程循環(huán)下去，直到左邊的序號等于右邊的序號蜕煌，兩個相等序號所在的位置就是基準值應該存在的位置派阱，將這個位置的值賦值為基準值。
5.這時會出現(xiàn)一個現(xiàn)象斜纪，基準數(shù)左邊的數(shù)都是比他小的贫母，右邊的數(shù)都是比它大的。
6.然后就可以利用分治和遞歸的思想盒刚，分別對基準值左邊的區(qū)間進行排序颁独，對右邊的區(qū)間進行排序。這個過程是一個遞歸的過程伪冰，而遞歸必然存在一個出口誓酒，遞歸的出口就是排序區(qū)間的長度為0。
代碼實現(xiàn)
這里用java來簡單實現(xiàn)一下贮聂。
public static void quickSort(int[] num,int left,int right){
//遞歸的出口
if(left>=right){
return;
}
//獲取基準值所在的索引
int res = particular（num,left,right）;
//對左區(qū)間進行排序
quickSort(num,left,res-1);
//對右區(qū)間進行排序
quickSort(num,res+1,right);
}
public static int particular(int[] num,int left,int right){
//確定一個基準值靠柑，這里的基準值確定為最右邊的數(shù)
int base = num[right];
while(left<right){
while(num[left]<base&&left<right){
left++;
}
if(left<right){
num[right]=num[left];
right--;
}
while(num[right]>base&&left<right){
right--;
}
if(left<right){
num[left]=num[right];
left++;
}
}
//循環(huán)結束
//此時left==right，而這個位置就是基準值在數(shù)組中應該在的位置
num[left]=base;
//最后返回基準值所在的位置
return left;
}
算法優(yōu)化
- 三平均分區(qū)法
關于這一改進的最簡單的描述大概是這樣的：與一般的快速排序方法不同吓懈，它并不是選擇待排數(shù)組的第一個數(shù)作為中軸歼冰，而是選用待排數(shù)組最左邊、最右邊和最中間的三個元素的中間值作為中軸耻警。這一改進對于原來的快速排序算法來說隔嫡，主要有兩點優(yōu)勢：
首先甸怕，它使得最壞情況發(fā)生的幾率減小了。
其次腮恩，未改進的快速排序算法為了防止比較時數(shù)組越界梢杭，在最后要設置一個哨點。
根據(jù)分區(qū)大小調整算法
這一方面的改進是針對快速排序算法的弱點進行的秸滴∥淦酰快速排序對于小規(guī)模的數(shù)據(jù)集性能不是很好〉春可能有人認為可以忽略這個缺點不計咒唆，因為大多數(shù)排序都只要考慮大規(guī)模的適應性就行了。但是快速排序算法使用了分治技術释液，最終來說大的數(shù)據(jù)集都要分為小的數(shù)據(jù)集來進行處理全释。由此可以得到的改進就是，當數(shù)據(jù)集較小時误债，不必繼續(xù)遞歸調用快速排序算法浸船，而改為調用其他的對于小規(guī)模數(shù)據(jù)集處理能力較強的排序算法來完成。Introsort就是這樣的一種算法找前，它開始采用快速排序算法進行排序，當遞歸達到一定深度時就改為堆排序來處理判族。這樣就克服了快速排序在小規(guī)模數(shù)據(jù)集處理中復雜的中軸選擇躺盛，也確保了堆排序在最壞情況下O(n log n)的復雜度。
另一種優(yōu)化改進是當分區(qū)的規(guī)模達到一定小時形帮，便停止快速排序算法槽惫。也即快速排序算法的最終產物是一個“幾乎”排序完成的有序數(shù)列。數(shù)列中有部分元素并沒有排到最終的有序序列的位置上辩撑，但是這種元素并不多界斜。可以對這種“幾乎”完成排序的數(shù)列使用插入排序算法進行排序以最終完成整個排序過程合冀。因為插入排序對于這種“幾乎”完成的排序數(shù)列有著接近線性的復雜度各薇。這一改進被證明比持續(xù)使用快速排序算法要有效的多。
另一種快速排序的改進策略是在遞歸排序子分區(qū)的時候君躺，總是選擇優(yōu)先排序那個最小的分區(qū)峭判。這個選擇能夠更加有效的利用存儲空間從而從整體上加速算法的執(zhí)行。不同的分區(qū)方案考慮
對于快速排序算法來說棕叫，實際上大量的時間都消耗在了分區(qū)上面林螃，因此一個好的分區(qū)實現(xiàn)是非常重要的。尤其是當要分區(qū)的所有的元素值都相等時俺泣，一般的快速排序算法就陷入了最壞的一種情況疗认，也即反復的交換相同的元素并返回最差的中軸值完残。無論是任何數(shù)據(jù)集，只要它們中包含了很多相同的元素的話横漏，這都是一個嚴重的問題谨设，因為許多“底層”的分區(qū)都會變得完全一樣。
對于這種情況的一種改進辦法就是將分區(qū)分為三塊而不是原來的兩塊：一塊是小于中軸值的所有元素绊茧，一塊是等于中軸值的所有元素铝宵，另一塊是大于中軸值的所有元素。另一種簡單的改進方法是华畏，當分區(qū)完成后鹏秋，如果發(fā)現(xiàn)最左和最右兩個元素值相等的話就避免遞歸調用而采用其他的排序算法來完成。并行的快速排序
由于快速排序算法是采用分治技術來進行實現(xiàn)的亡笑，這就使得它很容易能夠在多臺處理機上并行處理侣夷。
在大多數(shù)情況下，創(chuàng)建一個線程所需要的時間要遠遠大于兩個元素比較和交換的時間仑乌，因此百拓，快速排序的并行算法不可能為每個分區(qū)都創(chuàng)建一個新的線程。一般來說晰甚，會在實現(xiàn)代碼中設定一個閥值衙传，如果分區(qū)的元素數(shù)目多于該閥值的話，就創(chuàng)建一個新的線程來處理這個分區(qū)的排序厕九，否則的話就進行遞歸調用來排序蓖捶。
對于這一并行快速排序算法也有其改進。該算法的主要問題在于扁远，分區(qū)的這一步驟總是要在子序列并行處理之前完成俊鱼，這就限制了整個算法的并行程度。解決方法就是將分區(qū)這一步驟也并行處理畅买。改進后的并行快速排序算法使用2n個指針來并行處理分區(qū)這一步驟并闲，從而增加算法的并行程度。
快速排序算法的變種
隨機化快排
快速排序的最壞情況基于每次劃分對主元的選擇谷羞〉刍穑基本的快速排序選取第一個元素作為主元。這樣在數(shù)組已經有序的情況下湃缎，每次劃分將得到最壞的結果购公。一種比較常見的優(yōu)化方法是隨機化算法，即隨機選取一個元素作為主元雁歌。這種情況下雖然最壞情況仍然是O(n^2)宏浩，
但最壞情況不再依賴于輸入數(shù)據(jù)，而是由于隨機函數(shù)取值不佳靠瞎。實際上比庄，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n)求妹。所以隨機化快速排序可以對于絕大多數(shù)輸入數(shù)據(jù)達到O(nlogn)的期望時間復雜度。一位前輩做出了一個精辟的總結：“隨機化快速排序可以滿足一個人一輩子的人品需求佳窑。
隨機化快速排序的唯一缺點在于制恍，一旦輸入數(shù)據(jù)中有很多的相同數(shù)據(jù)，隨機化的效果將直接減弱神凑。對于極限情況净神，即對于n個相同的數(shù)排序，隨機化快速排序的時間復雜度將毫無疑問的降低到O(n^2)溉委。解決方法是用一種方法進行掃描鹃唯，使沒有交換的情況下主元保留在原位置。平衡快排
每次盡可能地選擇一個能夠代表中值的元素作為關鍵數(shù)據(jù)瓣喊，然后遵循普通快排的原則進行比較坡慌、替換和遞歸。通常來說藻三，選擇這個數(shù)據(jù)的方法是取開頭洪橘、結尾、中間3個數(shù)據(jù)棵帽，通過比較選出其中的中值熄求。取這3個值的好處是在實際問題中，出現(xiàn)近似順序數(shù)據(jù)或逆序數(shù)據(jù)的概率較大逗概，此時中間數(shù)據(jù)必然成為中值弟晚，而也是事實上的近似中值。萬一遇到正好中間大兩邊姓套弧（或反之）的數(shù)據(jù)指巡，取的值都接近最值淑履，那么由于至少能將兩部分分開隶垮，實際效率也會有2倍左右的增加，而且利于將數(shù)據(jù)略微打亂秘噪，破壞退化的結構狸吞。外部快排
與普通快排不同的是，關鍵數(shù)據(jù)是一段buffer指煎，首先將之前和之后的M/2個元素讀入buffer并對該buffer中的這些元素進行排序蹋偏，然后從被排序數(shù)組的開頭（或者結尾）讀入下一個元素，假如這個元素小于buffer中最小的元素至壤，把它寫到最開頭的空位上威始；假如這個元素大于buffer中最大的元素，則寫到最后的空位上像街；否則把buffer中最大或者最小的元素寫入數(shù)組黎棠，并把這個元素放在buffer里晋渺。保持最大值低于這些關鍵數(shù)據(jù)，最小值高于這些關鍵數(shù)據(jù)脓斩，從而避免對已經有序的中間的數(shù)據(jù)進行重排木西。完成后，數(shù)組的中間空位必然空出随静，把這個buffer寫入數(shù)組中間空位八千。然后遞歸地對外部更小的部分，循環(huán)地對其他部分進行排序燎猛。三路基數(shù)快排
（Three-way Radix Quicksort恋捆，也稱作Multikey Quicksort、Multi-key Quicksort）：結合了基數(shù)排序（radix sort扛门，如一般的字符串比較排序就是基數(shù)排序）和快排的特點鸠信，是字符串排序中比較高效的算法。該算法被排序數(shù)組的元素具有一個特點论寨，即multikey星立，如一個字符串，每個字母可以看作是一個key葬凳。算法每次在被排序數(shù)組中任意選擇一個元素作為關鍵數(shù)據(jù)绰垂，首先僅考慮這個元素的第一個key（字母），然后把其他元素通過key的比較分成小于火焰、等于劲装、大于關鍵數(shù)據(jù)的三個部分。然后遞歸地基于這一個key位置對“小于”和“大于”部分進行排序昌简，基于下一個key對“等于”部分進行排序占业。
時間復雜度分析
最壞情況：O(n ^ 2)
最好情況：θ(nlogn)
平均情況：θ(nlogn)
