注：發此文謹以記錄初學《資料結構與算法分析——C語言描述》的個人了解，希望能夠得到寶貴意見與建議。（文中轉載有相關文章片段，在學習時幫助了解作用較大，在此對作者表示感謝）
7.1 預備知識
1，算法接收 含元素的數組和包含元素個數的整數
2，基于比較的排序
7.2 插入排序
代碼實作
void InsertionSort(ElementType A[],int N)
{
int i,j;
ElementType Tmp;
for(i = 1 ; i < N ; i++)
{
Tmp = A[i];
for(j = i ; j > 0 && A[j - 1] > Tmp ; j--)
{
A[j] = A[j - 1];
}
A[j] = Tmp;//避免明顯使用交換
}
} 了解描述
位置i上元素存于Tmp中，i之前所有更大的元素向右移一位（i前所有元素已排序），Tmp被置于正确位置。
分析
1，（未排序）嵌套循環每個花費N次疊代，為O(N^2)
2，（已排序）為O(N)
*由于差距較大，故值得分析平均情形
7.3 一些簡單排序算法的下界
1，怎樣概括“一些”的共性？
引入逆序 —— 插排交換次數=逆序數（O(N) <=> O(N + I),N:其他工作，I:逆序數）—— 平均運作時間 <=> 平均逆序數
* 以插排為例分析（插排 代表 通過交換相鄰元素進行排序的算法），得出共性
2，結論
定理7.1 N個互異數的數組的平均逆序數是N(N-1)/4
定理7.2 通過交換相鄰元素進行排序的任何算法平均需要Ω(N^2)時間
7.4 希爾排序
代碼實作
void ShellSort(ElementType A[],int N)
{
int i,j,Increment;
ElementType Tmp;
for(Increment = N / 2 ; Increment > 0 ; Increment /= 2)
{
for(i = Increment ; i < N ; i++)//小型插排
{
Tmp = A[i];
for(j = i ; j >= Increment && A[j - Increment] > Tmp ; j -= Increment)
{
A[j] = A[j - Increment];
}
A[j] = Tmp;
}
}
} 了解描述
不斷縮小增量的插入排序，通過遠距離交換以達到一次消除多對逆序（需保證增量變換時不幹擾已處理的順序），減小每一趟工作量，即亞二次運作時間。
分析
定理7.3 使用希爾增量的希爾排序的最壞運作時間為Θ(N^2)
定理7.4 使用 Hibbard 增量的希爾排序的最壞運作時間為Θ(N^2) (Hibbard增量形如 1,3,7,...,2^k - 1)
7.5 堆排序
代碼實作
#define LeftChild(i) (2 * (i) + 1)//下标從0開始,是以為 2*i+1
void PercDown(ElementType A[],int i,int N)
{
int Child;
ElementType Tmp;
for(Tmp = A[i] ; LeftChild(i) < N ; i = Child)//下标從0開始,注意邊界
{
Child = LeftChild(i);
if(Child != N - 1 && A[Child + 1] > A[Child])//Child != N - 1 即右邊還有資料
{
Child++;//選出較大的兒子
}
if(Tmp < A[Child])
{
A[i] = A[Child];
}
else
{
break;
}
}
A[i] = Tmp;
}
void HeapSort(ElementType A[] , int N)
{
int i;
//BuildHeap
for(i = N / 2 ; i >= 0 ; i--)//從右向左,從下向上,逐漸下濾
{
PercDown(A,i,N);
}
//DeleteMax
for(i = N - 1 ; i > 0 ; i--)
{
Swap(&A[0] , &A[i]);
PercDown(A , 0 , i);//位置0處元素下濾,且元素個數改變
}
} 
上圖為建構初始堆及排序過程，數組中表,97.58,31,26,41,58,31
了解描述
1，對已有數組元素進行整理，建構max堆（max堆便于實施從小到大排序）
2，排序時通過回收利用空間，避免使用第二個數組
分析
定理7.5 對N個互異項的随機排列進行堆排序，所用的平均比較次數為 2NlogN - O(NlogN)
7.6歸并排序
代碼實作
void MergeSort(ElementType A[],int N)//驅動例程
{
ElementType *TmpArray;
TmpArray = malloc(N * sizeof(ElementType));
if(TmpArray != NULL)
{
MSort(A,TmpArray,0,N - 1);
free(TmpArray);
}
else
{
FatalError("No space for tmp array");
}
}
void MSort(ElementType A[],ElementType TmpArray[],int Left,int Right)
{
int Center;
if(Left < Right)//條件成立時再對Center指派
{
Center = (Left + Right) / 2;
MSort(A , TmpArray , Left , Center);
MSort(A , TmpArray , Center + 1 , Right);
Merge(A , TmpArray , Left , Center + 1 , Right);//Center + 1 即右半部分始位置
}
}
void Merge(ElementType A[] , ElementType TmpArray[] , int Lpos , int Rpos , int RightEnd)
{
int i , LeftEnd , TmpPos , NumElements;
//NumElements 存放每次排序時元素總數(臨時數組元素轉移至原數組時使用)
//TmpPos 記錄排序元素在建立數組中*對應*位置
LeftEnd = Rpos - 1;
NumElements = RightEnd - Lpos;
TmpPos = Lpos;
while(Lpos < LeftEnd && Rpos < RightEnd)
{
if(A[Lpos] < A[Rpos])
{
TmpArray[TmpPos++] = A[Lpos++];
}
else
{
TmpArray[TmpPos++] = A[Rpos++];
}
}
//Copy rest of each half
while(Lpos <= LeftEnd)
{
TmpArray[TmpPos++] = A[Lpos++];
}
while(Rpos <= RightEnd)
{
TmpArray[TmpPos++] = A[Rpos++];
}
for(i = 0 ; i < NumElements ; i++ , RightEnd--)
{
A[RightEnd] = TmpArray[RightEnd];
}
} 了解描述
1，遞歸是怎樣實施的？
答：以8個元素為例，左右各分成4 個元素，先處理左邊4 個，将左邊4個元素重複分隔，直到左邊隻剩一個元素，達到基準條件，傳回最近主程式中，處理右邊一個元素，達到基準條件，進行合并，此時這兩個元素作為左側，傳回最近主程式中，處理右邊兩個元素，繼續先左後右，處理合并，傳回最近主程式中，進行合并。此時總體來看，8個元素，左側4個已實施“分治”，接下來繼續進行遞推，過程類似。
2，小塊元素合并後怎樣存放？
答：小塊元素在臨時數組*對應位置*進行合并存放，排序後依次放入原數組中，不影響後面元素及其排序。
分析
運作時間：T(N) = O(NlogN)
應用：很難用于主存排序。首先，合并兩個線性表需要線性附加記憶體，其次，資料在數組間拷貝需要時間。
7.7 快速排序
代碼實作
//驅動例程
void QuickSort(ElementType A[] , int N)
{
QSort(A , 0 , N - 1);
}
//選取樞紐元
//對三元素排序，最值放兩邊，樞紐元置于 right-1 處(此方法便于設定警戒标志，防止越界)
ElementType Median3(ElementType A[] , Left , Right)
{
int Center;
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]);
return A[Right - 1];
}
#define Cutoff (3)
void QSort(ElementType A[] , int Left , int Right)
{
int i , j;
ElementType Pivot;
if(Left + Cutoff <= Right)//數組内大于3個元素時，分割加遞歸
{
Pivot = Median3(A , Left , Right);
i = Left;//因為下方使用的是前自增
j = Right - 1;
for( ; ; )
{
while(A[++i] < Pivot){}
while(A[--j] > Pivot){}
if(i < j)
{
Swap(&A[i],&A[j]);
}
else
{
break;
}
}
Swap(&A[i],&A[Right - 1]);//Restore pivot
QSort(A , Left , i - 1);
QSort(A , i + 1 , Right);
}
else
{
InsertionSort(A + Left , Right - Left + 1);
}
} 了解描述
與歸并排序類似，差別是選取樞紐元，以樞紐元為界分割為大小兩數組。（适用于大數組）
選取樞紐元：随機選取；三數中值分割法（左，右，中心位置裡的中值,同時将三元素排序，便于設定警戒标志，防止越界）
分割政策：1，樞紐元與位置right - 1處元素互換
2，設定i（left）,j（right - 1），i 向右滑動直至 i 處元素 >= 樞紐元，j 向左滑動直至 j 處元素 <= 樞紐元，交換i，j處元素
3，i，j交錯時，i 處元素與樞紐元交換
分析
最壞情況分析：樞紐元始終為最小元素，T(N) = O(N^2)
最好情況分析：樞紐元位于中間，T(N) = O(NlogN)
平均情況分析：每個檔案大小等可能，求出平均分布，T(N) = O(NlogN)
擴充（選擇問題的線性期望時間算法）
選擇問題：查找集合S中第k個最小元
與快速排序類似，差別在于分割後，若 k <= |S1|,則傳回quickselect( S1 , k )，若k = |S1| + 1 ，則樞紐元即為所求，否則傳回quickselect(S2 , k - |S1| - 1)
代碼實作
#define Cutoff (3)
void QuickSelect(ElementType A[] , int k , int N)
{
QSelect(A , k , 0 , N - 1);
}
ElementType Median3(ElementType A[] , Left , Right)
{
int Center;
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]);
return A[Right - 1];
}
//位置k - 1處即為第k個最小值
void QSelect(ElementType A[] , int k , int Left , int Right)
{
int i , j;
ElementType Pivot;
if(Left + Cutoff <= Right)
{
Pivot = Median3(A , Left , Right);
i = Left;
j = Right - 1;
for( ; ; )
{
while(A[++i] < Pivot){}
while(A[--j] > Pivot){}
if(i < j)
{
Swap(&A[i],&A[j]);
}
else
{
break;
}
}
Swap(&A[i],&A[Right - 1]);//Restore pivot
if(k <= i)
{
QSelect(A , k , Left , i - 1);
}
else if(k > i + 1)
{
QSelect(A , k - i - 1 , i + 1 , Right);
}
}
else
{
InsertionSort(A + Left , Right - Left + 1);
}
} 7.8 大型結構的排序
排序時交換整個結構代價是昂貴的，解決辦法是讓輸入數組包含指向結構的指針，通過指針比較關鍵字，必要時交換指針來進行排序。
7.9 排序的一般下界
引入決策樹，通過隻使用比較進行排序的每一種算法都可以用決策樹表示。
引理7.1：令T是深度為d的二叉樹，則T最多有2^d個樹葉
引理7.2：具有L片樹葉的二叉樹深度至少是[ logL ]
定理7.6：隻使用元素間比較的任何排序算法在最壞情況下至少需要[ log( N! ) ]次比較
定理7.7：隻使用元素間比較的任何排序算法需要進行Ω(NlogN)次比較
7.10 桶式排序
以線性時間進行排序，建構數組，大小包含所有待排元素，初始為0，元素出現以1代替。
7.11 外部排序
簡單算法（該部分内容轉自@Judy518）——二路合并
例如要對外存中4500個記錄進行歸并，而記憶體大小隻能容納750個記錄，在第一階段，我們可以每次讀取750個記錄進行排序，這樣可以分六次讀取，進行排序，可以得到六 個有序的歸并段，如下圖：
每個歸并段的大小是750個記錄，記住，這些歸并段已經全部寫到臨時緩沖區（由一個可用的磁盤充當）内了，這是第一步的排序結果。
1、将記憶體空間劃分為三份，每份大小250個記錄，其中兩個用作輸入緩沖區，另外一個用作輸出緩沖區。首先對Segment_1和Segment_2進行歸并，先從每個歸并段中讀取250個記錄到輸入緩沖區，對其歸并，歸并結果放到輸出緩沖區，當輸出緩沖區滿後，将其寫道臨時緩沖區内，如果某個輸入緩沖區空了，則從相應的歸并段中再讀取250個記錄進行繼續歸并，反複以上步驟，直至Segment_1和Segment_2全都排好序，形成一個大小為1500的記錄，然後對Segment_3和Segment_4、Segment_5和Segment_6進行同樣的操作。
2、對歸并好的大小為1500的記錄進行如同步驟1一樣的操作，進行繼續排序，直至最後形成大小為4500的歸并段，至此，排序結束。
多路合并
1，2-路合并擴充為k-路合并，差別在于尋找k個元素中最小元過程稍微複雜，可通過優先隊列尋找最小元，進行DeleteMin操作，得到下一個寫到磁盤上的元素
2，在初始順串構造階段之後，k-路合并所需趟數為[ logk( N / M ) ]。（N為資料總量，M為記憶體容量）
多相合并
k-路合并需要2k盤錄音帶，然而使用 k + 1 盤錄音帶也有可能完成排序工作，作為例子，這裡闡述隻用三盤錄音帶（T1,T2,T3）如何完成2-路合并。
假設T1上有一個輸入檔案，它将産生34個順串。
選擇一：每盤錄音帶存入17個，然後合并存放至T1，再将T1前個8順串存至T2，再次合并存至T3，依次類推。這樣每一趟合并附加額外半趟工作。
選擇二：将34個順串不均衡地分成2份，例如21,13，再次進行合并。此時需考慮順串最初的配置設定，事實上，若初始順串為斐波那契數，則将其分裂為2個斐波那契數之和，否則需添加啞順串填補錄音帶，将其補足為斐波那契數
替換選擇（該部分内容轉自@kph_Hajash）
在标準的外排中，一次讀入記憶體可容納的 M 個記錄，排序完依次輸出到空錄音帶上；但這裡其實有個小技巧，排完序後輸出第一個記錄到錄音帶上時，記憶體讓出了一個記錄的空間，這時我們可以從輸入錄音帶取出一個記錄，判斷它是否大于剛輸出的記錄，若是，說明它可以放入目前順串中（順串是從小到大有序），否則，應暫存記憶體，等下一個順串的構造； 這裡暫存記憶體書上講是放在最小堆的死區（dead space）。
初始順串的構造詳解，綠色箭頭表示目前輸入狀态，Tbn 表示輸出狀态，記憶體緩沖表示目前記憶體中存在的記錄（括号内記錄表示存在最小堆的死區）