常見的內排序算法
所謂的內排序是指所有的數據已經讀入內存，在內存中進行排序的算法。排序過程中不需要對磁盤進行讀寫。同時，內排序也一般假定所有用到的輔助空間也可以直接存在于內存中。與之對應地，另一類排序稱作外排序，即內存中無法保存全部數據，需要進行磁盤訪問，每次讀入部分數據到內存進行排序。我們在9.1.2“常見的外排序算法”中討論該類問題。
1．合并排序
合并排序（Merge Sort）是一種典型的排序算法，應用“分而治之（divide and conquer）”的算法思路，將線性數據結構（如array、vector或list）分為兩個部分，對兩部分分別進行排序，排序完成后，再將各自排序好的兩個部分合并還原成一個有序結構。由于合并排序不依賴于隨機讀寫，因此具有很強的普適性，適用于鏈表等數據結構。算法的時間復雜度為O(nlogn)，如果是處理數組需要額外O（n）空間，處理鏈表只需要O（1）空間。算法實現如下：
void merge_sort( int array[], int helper[], int left, int right){
if( left >= right )
return;
// divide and conquer: array will be divided into left part and right part
// both parts will be sorted by the calling merge_sort
int mid = right - (right - left) / 2;
merge_sort( array, helper, left, mid );
merge_sort( array, helper, mid + 1, right);
// now we merge two parts into one
int helperLeft = left;
int helperRight = mid + 1;
int curr = left;
for(int i = left; i <= right; i++)
helper[i] = array[i];
while( helperLeft <= mid && helperRight <= right ){
if( helper[helperLeft] <= helper[helperRight] )
array[curr++] = helper[helperLeft++];
else
array[curr++] = helper[helperRight++];
}
// left part has some large elements remaining. Put them into the right side
while( helperLeft <= mid )
array[curr++] = helper[helperLeft++];
}
當遞歸調用merge_sort返回時，array的左右兩部分已經分別由子函數排序完成，我們利用helper數組暫存array中的數值，再利用兩個while循環完成合并。helper數組的左右半邊就是兩個排序完的隊列，第一個while循環相當于比較隊列頭，將較小的元素取出放入array，最后使得array的左半邊由小到大排序完成。第二個while循環負責掃尾，把helper左半邊剩余元素復制入array中。注意，此時我們不需要對helper右半邊做類似操作，因為即使右半邊有剩余元素，它們也已經處于array中恰當的位置。
關于合并排序更多理論方面的討論，請見9.3“工具箱”。
2．快速排序
快速排序（Quick Sort）是最為常用的排序算法，C++自帶的排序算法的實現就是快速排序。該算法以其高效性，簡潔性，被評為20世紀十大算法之一（雖然合并排序與堆排序的時間復雜度量級相同，但一般還是比快速排序慢常數倍）?？焖倥判虻乃惴ê诵呐c合并排序類似，也采用“分而治之”的想法：隨機選定一個元素作為軸值，利用該軸值將數組分為左右兩部分，左邊元素都比軸值小，右邊元素都比軸值大，但它們不是完全排序的。在此基礎上，分別對左右兩部分遞歸調用快速排序，使得左右部分完全排序。算法的平均時間復雜度是O(nlogn)，在最壞情況下為O(n^2)，額外空間復雜度為O(logn)。算法實現如下：
int partition( int array[], int left, int right ) {
int pivot = array[right];
while( left != right ){
while( array[left] < pivot && left < right)
left++;
if (left < right) {
swap( array[left], array[right--]);
}
while( array[right] > pivot && left < right)
right--;
if( left < right )
swap( array[left++], array[right]);
}
//array[left] = pivot;
return left;
}
void qSort( int array[], int left, int right ){
if( left >=right )
return;
int index = partition( array, left, right);
qSort(array, left, index - 1);
qSort(array, index + 1, right);
}
partition函數先選定數組right下標所指的元素作為軸值，用pivot變量存儲該元素值。然后，右移left，即從左向右掃描數組，直到發現某個元素大于軸值或者掃描完成。如果某個元素大于軸值，則將該元素與軸值交換。該操作特性在于：保證交換后軸值左側的元素都比軸值小。再次，左移right，即從右向左掃描數組，直到發現某個元素小于軸值或者掃描完成。如果某個元素小于軸值，則將該元素與軸值交換。該操作特性在于：保證交換后軸值右側的元素都比軸值大。重復上述過程直到left和right相遇，最終相遇的位置即為軸值所在位置。由于上述操作的特性，最終軸值左側的元素都比軸值小，軸值右側的元素都比軸值大。
關于快速排序的更多理論討論請見9.3“工具箱”。C++標準模版庫提供函數sort，實現快速排序的功能：sort( iterator first, iterator last, Compare comp ); // can also be pointers here。
3．堆排序
堆排序（Heap Sort）利用了我們在第5章中提到的堆作為邏輯存儲結構，將輸入array變成一個最大值堆。然后，我們反復進行堆的彈出操作?；仡欀八龅膹棾鲞^程：將堆頂元素與堆末元素交換，堆的大小減一，向下移動新的堆頂以維護堆的性質。事實上，該操作等價于每次將剩余的最大元素移動到數組的最右邊，重復這樣的操作最終就能獲得由小到大排序的數組。初次建堆的時間復雜度為O(n)，刪除堆頂元素并維護堆的性質需要O(logn)，這樣的操作一共進行n次，故最終時間復雜度為O(nlogn)。我們不需要利用額外空間，故空間復雜度O(1)。具體實現如下：
void heapSort(int array[], int size) {
Heapify(array, size);
for (int i = 0; i < size - 1; i++)
popHeap(array);
}
Heapify和popHeap的實現參考本書第5章。
4．桶排序和基數排序
桶排序（Bucket Sort）和基數排序（Radix Sort）不需要進行數據之間的兩兩比較，但是需要事先知道數組的一些具體情況。特別地，桶排序適用于知道待排序數組大小范圍的情況。其特性在于將數據根據其大小，放入合適的“桶（容器）”中，再依次從桶中取出，形成有序序列。具體實現如下：
void BucketSort(int array[], int n, int max)
{
// array of length n，all records in the range of [0,max)
int tempArray[n];
int i;
for (i = 0; i < n; i++)
tempArray[i] = array[i];
int count[max]; // buckets
memset(count, 0, max * sizeof(int));
for (i = 0; i < n; i++) // put elements into the buckets
count[array[i]]++;
for (i = 1; i < max; i++)
count[i] = count[i-1] + count [i]; // count[i] saves the starting index (in array) of value i+1
// for value tempArray[i], the last index should be count[tempArray[i]]-1
for (i = n-1; i >= 0; i--)
array[--count[tempArray[i]]] = tempArray[i];
}
該實現總的時間代價為O(max+n)，適用于max相對n較小的情況?？臻g復雜度也為O(max+n)，用以記錄原始數組和桶計數。
桶排序只適合max很小的情況，如果數據范圍很大，可以將一個記錄的值即排序碼拆分為多個部分來進行比較，即使用基數排序?；鶖蹬判蛳喈斢趯祿醋饕粋€個有限進制數，按照由高位到低位（適用于字典序），或者由低位到高位（適用于數值序）進行排序。排序具體過程如下：對于每一位，利用桶排序進行分類，在維持相對順序的前提下進行下一步排序，直到遍歷所有位。該算法復雜度為O(k*n)，k為位數（或者字符串長度）。直觀上，基數排序進行了k次桶排序。具體實現如下：
void RadixSort(int Array[], int n, int digits, int radix)
{
// n is the length of the array
// digits is the number of digits
int *TempArray = new int[n];
int *count = new int[radix]; // radix buckets
int i, j, k;
int Radix = 1; // radix modulo, used to get the ith digit of Array[j]
// for ith digit
for (i = 1; i <= digits; i++) {
for (j = 0; j < radix; j++)
count[j] = 0; // initialize counter
for (j = 0; j < n; j++) {
// put elements into buckets
k = (Array[j] / Radix) % radix; // get a digit
count[k]++;
}
for (j = 1; j < radix; j++) {
// count elements in the buckets
count[j] = count[j-1] + count[j];
}
// bucket sort
for (j = n-1; j >= 0; j--) {
k = (Array[j] / Radix ) % radix;
count[k]--;
TempArray[count[k]] = Array[j];
}
for (j = 0; j < n; j++) {
// copy data back to array
Array[j] = TempArray[j];
}
Radix *= radix; // get the next digit
}
}
與其他排序方式相比，桶排序和基數排序不需要交換或比較，它更像是通過逐級的分類來把元素排序好。
常見的外排序算法
外排序算法的核心思路在于把文件分塊讀到內存，在內存中對每塊文件依次進行排序，最后合并排序后的各塊數據，依次按順序寫回文件。外排序需要進行多次磁盤讀寫，因此執行效率往往低于內排序，時間主要花費于磁盤讀寫上。我們給出外排序的算法步驟如下：
假設文件需要分成k塊讀入，需要從小到大進行排序。
（1）依次讀入每個文件塊，在內存中對當前文件塊進行排序（應用恰當的內排序算法）。此時，每塊文件相當于一個由小到大排列的有序隊列。
（2）在內存中建立一個最小值堆，讀入每塊文件的隊列頭。
（3）彈出堆頂元素，如果元素來自第i塊，則從第i塊文件中補充一個元素到最小值堆。彈出的元素暫存至臨時數組。
（4）當臨時數組存滿時，將數組寫至磁盤，并清空數組內容。
（5）重復過程（3）、（4），直至所有文件塊讀取完畢。
本文節選自《程序員面試白皮書》
