快排是一種使用廣泛的排序，它比merge需要的空間更小懈万，而且改進(jìn)過的快排速度很快拴清，平均O(nlgn)靶病。快排也用到了遞歸的思想口予，所以我才說遞歸很重要的嘛娄周。
我們大概看一下快排的基本過程：選擇一個(gè)數(shù)，把小于它的放左邊沪停，不小于它的放右邊煤辨。沒了。那么很顯然木张，這個(gè)算法的特點(diǎn)和難點(diǎn)就是“怎么選出一個(gè)合適的點(diǎn)”和“怎么實(shí)現(xiàn)‘放’”众辨。選擇肯定是超重要的，還記得上一節(jié)的“遞歸樹”嗎舷礼，如果采用“二路歸并”泻轰，在這里就是分為2個(gè)序列，那么最好是把分開的點(diǎn)選在中間且轨，因?yàn)闃涓呤峭ㄟ^最長路徑來計(jì)算的浮声。
另一個(gè)問題就是怎么實(shí)現(xiàn)這個(gè)“通過一個(gè)點(diǎn)把比它小的全放左邊比它大的全放右邊”。我們大概可以這樣做：一個(gè)flag從最左端開始移動(dòng)旋奢，一個(gè)flag從最右端開始移動(dòng)泳挥，當(dāng)碰到一個(gè)左側(cè)的點(diǎn)大于被選擇點(diǎn)，并且一個(gè)右側(cè)的點(diǎn)小于被選擇的點(diǎn)時(shí)至朗，交換它們屉符。
當(dāng)然，在執(zhí)行的時(shí)候我們可以把選中的那個(gè)點(diǎn)放在數(shù)組的最右邊锹引，當(dāng)然也可以不動(dòng)矗钟，比如我們直接選擇最左端和最右端的點(diǎn)當(dāng)作我們的判斷點(diǎn)。
那么我們來實(shí)現(xiàn)一哈：
//先實(shí)現(xiàn)一下主函數(shù)
template <typename T>
void QuickSort( T a[ ], int n )
{
if (n <= 1)
return;
Qsort( a, 0, n-1 );
} //是的嫌变，這就完了
哈哈吨艇，我們趕緊來實(shí)現(xiàn)一哈核心功能Qsort()：
template <typename T>
void Qsort( T a[ ], int Left, int Right )
{
if ( Left >= Right) //說明已經(jīng)不能再divide了
return;
int i = Left, j = Right;
T pivot = a[ Left ]; //選最左端點(diǎn)為pivot
while ( i < j )
{
while ( i < j && a[ j ] >= pivot ) //這里需要 i < j 為了控制不過界
--j; //當(dāng)a[ j ]比pivot大時(shí)，繼續(xù)遞減腾啥，直到減到不滿足條件
a[ i ] = a[ j ]; //把 j 位置上的值賦給 i 东涡，而第一個(gè)i正是pivot
while ( i < j && a[i] >= pivot )
++i;
a[ j ] = a[ i ]; //繼上，把這個(gè)i賦給j上一次的位置倘待，很巧妙吧
}
a[ i ] = pivot;
Qsort( a, Left, i - 1 );
Qsort( a, i + 1, Right ); //分別去i-1和i+1疮跑，跳過i
}
簡單分析一下，
1）為什么要從j開始計(jì)算呢凸舵？因?yàn)槲覀儼裵ivot設(shè)在了最左端祖娘，這個(gè)位置一定要當(dāng)作第一個(gè)被交換的位置，才能保證程序的順利運(yùn)行（所以如果pivot在最右端啊奄，你會(huì)了嗎渐苏？）掀潮。
2）為什么最后是a[ i ] = pivot;結(jié)尾呢？很簡單整以，回到程序，我們先從j計(jì)算峻仇，再計(jì)算i的移動(dòng)公黑，那么很顯然是把i的位置和pivot交換啊~~
不過，正如很多書上所說（就當(dāng)是吧）摄咆，因?yàn)楝F(xiàn)實(shí)中很多序列并不是完全無序的凡蚜，取第一個(gè)比較冒險(xiǎn)，有可能出現(xiàn)最差解吭从，所以有以下2種取法：
1.隨機(jī)（我感覺挺好的朝蜘，他們說計(jì)算量耗費(fèi)大）。
2.3數(shù)取中值：就是第1涩金，最后谱醇，中間3個(gè)元素取他們的中值作為pivot。實(shí)現(xiàn)方法很簡單：
void mid3( T a[], int L, int R )
{
int C = ( L + R ) / 2;
if ( a[ L ] > a[ C ] )
swap( a[ C ], a[ L ] );
if ( a[ C ] > a[ R ] )
swap( a[ C ], a[ R ] );
if ( a[ R ] > a[ L ] )
swap( a[ R ], a[ L ] );
swap( a[ C ], a[ Left + 1 ] );
return a[ Left + 1 ] ;
}
先講結(jié)果：分別把左中右3個(gè)數(shù)排序步做，然后把中數(shù)放到第2個(gè)位置副渴。當(dāng)然調(diào)用的時(shí)候也需稍作調(diào)整，此處不再贅述全度。
一個(gè)不需要注意的地方是：這3個(gè)數(shù)比較并無特別的規(guī)則煮剧，只需要兩兩比較就好了（C32=3而已）。
時(shí)間復(fù)雜度我就不證了将鸵，最壞是O(n2)勉盅，當(dāng)每次pivot都取第一個(gè)的時(shí)候。
堆排序我們先不講了顶掉，等到聊到優(yōu)先隊(duì)列的時(shí)候再說吧鸽斟。那么池颈，我們第一個(gè)話題似乎就結(jié)束了~~
BTW，你有沒有覺得用c++寫這段代碼好多啊，要不然垒迂，我們用python大概寫一下？
def qsort(a):
if len(a) <= 1:
return a
pivot = a[len(a)//2] # 使用py3.x基跑，2.x的話不需要//
left = [x for x in a if x < pivot]
mid = [x for x in a if x == pivot]
right = [x for x in a if x > pivot]
return qsort(left) + mid + qsort(right) # 已經(jīng)實(shí)現(xiàn)一次劃分了
是不是有點(diǎn)恐怖蒲障，這么復(fù)雜的算法，僅僅不到10行······
補(bǔ)充一個(gè)Python版普通實(shí)現(xiàn)：
def quick_sort(array, l, r):
if l < r:
q = partition(array, l, r)
quick_sort(array, l, q - 1)
quick_sort(array, q + 1, r)
def partition(array, l, r):
x = array[r]
i = l - 1
for j in range(l, r):
if array[j] <= x:
i += 1
array[i], array[j] = array[j], array[i]
array[i + 1], array[r] = array[r], array[i+1]
return i + 1
