－快速排序
算法概述：與歸并相似，分而治之
void Quicksort ( ElementType A[ ] , int N )
{
if ( n < 2 ) return ;
pivot = 從A[ ] 中選出一個(gè)主元；
將 S＝{ A[ ] \ pivot } 分成2個(gè)獨(dú)立子集：
A1 = { a屬于S | a <= pivot } 和
A3 = { a屬于S | a >= pivot } ;
A[ ] = Quicksort( A1 , N1 )并 { pivot }并Quicksort( A2 , N2 ) ;
}
選主元：
取中位數(shù)
ElementType Median3 ( ElementType A[ ] , int Left , int Right )
{
int Center = ( Left + Right ) / 2 ;
if ( A[ Left ] > A[ Center ] )
Swap ( &A[ Left ] ) , &A[ Center ] ) ;
if ( A[ Left ] > A[ Right ] )
Swap ( &A[ Left ] ) , &A[ Right ] ) ;
if ( A[ Center ] > A[ Right ] )
Swap ( &A[ Center ] ) , &A[ Right ] ) ;
Swap ( &A[ Center ] , &A[ Right - 1 ] ) ; // 將pivot藏到右邊
return A[ Right - 1 ] ; // 返回主元，它在Right - 1這個(gè)位置
}
子集劃分
每次選定主元并完成子集劃分后，主元插入的位置都是它的最終位置，它一次性放到了正確位置以后都不用移動(dòng)
如果有元素正好等于pivot，停下來(lái)交換？不交換，繼續(xù)移動(dòng)指針？比較后選擇交換
快速排序問(wèn)題：該算法用到遞歸，對(duì)于小規(guī)模數(shù)據(jù)（比如小于100的數(shù)據(jù)）可能還不如插入排序快
所以，當(dāng)遞歸的數(shù)據(jù)規(guī)模充分小，則停止遞歸，直接調(diào)用簡(jiǎn)單排序；在程序中定義一個(gè)Cutoff的閾值，小于該值則調(diào)用簡(jiǎn)單算法
算法實(shí)現(xiàn)：
void Quicksort ( ElementType A[ ] , int Left , int Right )
{
if ( Cutoff <= Right - Left ) {
Pivot = Median3 ( A , Left , Right ) ;
i = Left ; j = Right - 1 ; // 開(kāi)始做子集劃分
for ( ; ; ) {
while ( A[ ++ i ] < Pivot ) { }
while ( A[ - - j ] > Pivot ) { }
if ( i < j )
Swap ( &A[ i ] , &A[ j ] ) ;
else break ; // 子集劃分結(jié)束
}
Swap ( &A[ i ] , &A[ Right - 1 ] ) ;
Quicksort ( A , Left , i - 1 ) ;
Quicksort ( A , i + 1 , Right ) ;
}
else
Insertion_Sort ( A + Left , Right - Left + 1 ) ; // 當(dāng)超過(guò)Cutoff閾值，開(kāi)始用簡(jiǎn)單排序
}
統(tǒng)一接口：
void Quick_Sort ( ElementType A[ ] , int N )
{
Quicksort( A , 0 , N - 1 ) ;
}
－表排序
待排元素不是簡(jiǎn)單的數(shù)字而是比較大的結(jié)構(gòu)，移動(dòng)元素步驟不能忽略不計(jì)
排序過(guò)程中不需要移動(dòng)原始數(shù)據(jù)，而是移動(dòng)指向它們的指針，這樣的排序叫間接排序；
定義一個(gè)指針數(shù)組作為“表”（table），如果僅要求按順序輸出，則輸出：
A[ table[0] ], A[ table[1] ], …… , A[ table[N-1] ]
物理排序：
N個(gè)數(shù)字的排列由若干個(gè)獨(dú)立的環(huán)組成
將物理排序獨(dú)立成若干個(gè)獨(dú)立的操作，開(kāi)辟一個(gè)臨時(shí)空間，從環(huán)中取出一個(gè)元素暫時(shí)放入該空間，依次將該環(huán)中其他元素 一一放置到正確的位置，最后將取出的元素拿出放進(jìn)環(huán)中最后空出來(lái)的位置。
最好情況：初始即有序
最壞情況：有N/2個(gè)環(huán)，每個(gè)環(huán)包含2個(gè)元素，這是需要3N／2次元素移動(dòng)。（每移動(dòng)一對(duì)元素要走三步）
－基數(shù)排序
桶排序 eg：有N個(gè)學(xué)生，他們的成績(jī)是0到100之間的整數(shù)，如何在線性時(shí)間內(nèi)將學(xué)生按成績(jī)排序？
0到100之間一共有101（M）個(gè)成績(jī)值，給每個(gè)成績(jī)值建立一個(gè)桶，桶實(shí)際上是鏈表；每輸入的一個(gè)同學(xué)的成績(jī)，就按成績(jī)將該同學(xué)放入相對(duì)于的鏈表中
void Bucket_Sort ( ElementType A[ ] , int N )
{
count[ ] 初始化 ;
while ( 讀入1個(gè)學(xué)生成績(jī)grade )
將該學(xué)生插入count[ garde ]鏈表；
for ( i = 0 ; i < M ; i ++ ) { // M是成績(jī)值總數(shù)
if ( count[ i ] )
輸出整個(gè)count [ i ]鏈表；
}
}
基數(shù)排序 eg：假設(shè)有N＝10個(gè)整數(shù)，每個(gè)整數(shù)的值在0到999之間（于是有M＝1000個(gè)不同的值）此時(shí)再用桶排序則不合算
基數(shù)是進(jìn)制的基數(shù)，如0到999之間的數(shù)，最多是三位數(shù)，每個(gè)位上的基數(shù)有10種可能
輸入序列：64，8，216，512，27，729，0，1，343，125
用“次位優(yōu)先”（Least Significant Digit）即優(yōu)先比較個(gè)位
建立0～9十個(gè)桶，第一趟排序按照每個(gè)數(shù)字個(gè)位上的數(shù)放入相應(yīng)的桶，第二趟按十位上的數(shù)對(duì)應(yīng)放入相應(yīng)的桶，第三趟比百位數(shù)，
時(shí)間復(fù)雜度 T＝O（P（N＋B））
如果桶的數(shù)量足夠小，整個(gè)復(fù)雜度是線性的
多關(guān)鍵字排序，如撲克牌按花色、面值兩種關(guān)鍵字排序
多關(guān)鍵字可理解為多位數(shù)字，花色是十位，面值是個(gè)位
若用主位優(yōu)先，分為四個(gè)桶，再在每個(gè)桶里按面值排序
次位排序更為便捷，為面值建立13個(gè)桶；將結(jié)果合并，然后再為花色建四個(gè)桶
－排序算法的比較：
簡(jiǎn)單排序：簡(jiǎn)單選擇排序、冒泡排序、直接插入排序。
選擇排序是跳著交換的，導(dǎo)致其不穩(wěn)定性；簡(jiǎn)單排序時(shí)間復(fù)雜度較高，不過(guò)代碼較簡(jiǎn)單，其中冒泡排序和直接插入排序是穩(wěn)定的
希爾排序平均時(shí)間復(fù)雜度較低，但它的好壞取決于增量序列，不過(guò)最壞情況下時(shí)間復(fù)雜度依然是N的平方
堆排序和歸并排序，理論上，時(shí)間復(fù)雜度都是 N*logN，其中堆排序的N可能很大，所以某些情況下會(huì)比快速排序要慢，且它是不穩(wěn)定的；歸并排序是穩(wěn)定的，但需要一定空間；
快速排序是遞歸的，所以需要logN的空間復(fù)雜度，最壞情況下時(shí)間復(fù)雜度是N的平方，是不穩(wěn)定排序
基數(shù)排序某些情況下近乎線性，取決于桶
