排序
排序穩(wěn)定性
假設(shè)Ki=Kj（1<=i<=n,1<=j<=n,i!=j）集惋，且在排序前的序列中ri領(lǐng)先于rj。如果排序后ri仍領(lǐng)先于rj踩娘，則稱所用的排序方法時穩(wěn)定的刮刑；反之喉祭，若可能使得排序后的序列中rj領(lǐng)先ri，則稱所用的排序方法是不穩(wěn)定的雷绢。

image

image

歸并排序
歸并在數(shù)據(jù)結(jié)構(gòu)中的定義是將兩個或兩個以上的有序表組合成一個新的有序表。
歸并排序(Merging Sort)就是利用歸并的思想實(shí)現(xiàn)排序的方法钾唬。其原理是：假設(shè)初始含有n個記錄万哪，則可以看成是n個有序的子序列，每個子序列的長度為1抡秆，然后兩兩歸并壤圃，得到[n/2]個長度為2或1的有序子序列，再兩兩歸并琅轧，如此重復(fù)，直至得到一個長度為n的有序序列為止踊挠，這種排序方法稱為2路歸并排序乍桂。
一趟歸并排序需要將原數(shù)組的n個元素進(jìn)行兩兩歸并，將結(jié)果放到排序后的數(shù)組中效床，需要將待排的序列中的所有記錄掃描一遍睹酌，耗費(fèi)O[n]時間，同時由完全二叉樹的深度剩檀，整個歸并排序需要logn次,因此整體的時間復(fù)雜度為O[nlogn]
而在空間復(fù)雜度上憋沿，歸并排序在歸并過程中需要與原始記錄同樣數(shù)量的存儲空間存放歸并結(jié)果以及遞歸深度為logn的棧空間沪猴，因此辐啄，總的空間復(fù)雜度為n+logn
同時，歸并排序中由于存在兩兩比較运嗜，不存在跳躍壶辜，因此歸并排序是一種穩(wěn)定排序算法。

快速排序
快速排序與冒泡排序一樣屬于交換排序類担租≡颐瘢快速排序的實(shí)現(xiàn)，增大了記錄的比較和移動的距離奋救，將關(guān)鍵字較大的記錄從前面直接移動到后面岭参，關(guān)鍵字較小的記錄從后面直接移動到前面來，減少總的比較次數(shù)和移動交換次數(shù)尝艘。
快速排序的基本思想：
通過一趟排序?qū)⒋判蛴涗浄指畛煽瑟?dú)立的兩部分演侯，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序利耍，以達(dá)到整個序列有序的目的蚌本。
交換排序最好的情況下盔粹，中樞軸的分布正好是類似完全二叉樹的結(jié)構(gòu)，其時間復(fù)雜度為O[nlogn]
而如果是類似斜樹情況下(最壞情況)程癌，中樞軸每次都在最前端舷嗡，需要執(zhí)行n-1次遞歸調(diào)用，因此比較次數(shù)為n-1,n-2....1的求和嵌莉，即為n(n-1)/2,其時間復(fù)雜度為O[n^2]
空間復(fù)雜度进萄，主要是由于遞歸調(diào)用會造成相應(yīng)的棧空間使用锐峭，最好情況下中鼠，遞歸的深度為logn，空間復(fù)雜度為O[logn],最壞情況下沿癞，需要進(jìn)行n-1次遞歸援雇，因此空間復(fù)雜度為O[n]
**快速排序優(yōu)化： **

1. 中樞軸的選取
   基礎(chǔ)的快速排序中，在對子序列進(jìn)行分割找到中樞軸位置時椎扬，中樞軸開始都是選取固定的位置惫搏，因此如果固定位置處的中樞軸的關(guān)鍵字大小不合適會造成性能瓶頸，因此在中樞軸的選取上可以采取三數(shù)取中蚕涤。取三個關(guān)鍵字先進(jìn)行排序筐赔，將中間數(shù)作為中樞軸，一般取左端揖铜，右端和中間三個數(shù)茴丰。

2. 優(yōu)化不必要的交換
   在尋找中樞軸的位置時，不采用Swap交換的形式天吓，而是采用替換的形式

pivotKey = L->arr[low];
 L->arr[0] = pivotKey;
 while (low<high) {
    while (low < high&&L->arr[high] >= pivotKey)
    high--;
    //Swap(L, low, high);
    //使用替換代替交換贿肩，節(jié)省部分性能
    L->arr[low] = L->arr[high];
    while (low < high&&L->arr[low] <= pivotKey)
    low++;
    //Swap(L, low, high);
    //使用替換代替交換，節(jié)省部分性能
    L->arr[high] = L->arr[low];
 }
 L->arr[low] = L->arr[0];
 return low;   

3.優(yōu)化小數(shù)組時的排序方案
當(dāng)使用小數(shù)組時失仁，可以使用直接插入排序尸曼，而不是繼續(xù)使用快速排序來提高整體性能，因此可以檢測排序長度萄焦，當(dāng)長度大于某個定值時采用快速排序控轿，而小于某個定值時，直接使用插入排序拂封。

4.優(yōu)化遞歸操作
通過減少遞歸次數(shù)來提高性能

//減少遞歸次數(shù)優(yōu)化整體性能
 while (low < high) {
    pivot = Partition(L, low, high);
    QSort(L, low, pivot - 1);
    low=pivot+1;
 }
 //pivot = Partition(L, low, high);
 //QSort(L, low, pivot - 1);
 //QSort(L, pivot+1, high);