常见的内排序算法
所谓的内排序是指所有的数据已经读入内存，在内存中进行排序的算法。排序过程中不需要对磁盘进行读写。同时，内排序也一般假定所有用到的辅助空间也可以直接存在于内存中。与之对应地，另一类排序称作外排序，即内存中无法保存全部数据，需要进行磁盘访问，每次读入部分数据到内存进行排序。我们在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世纪十大算法之一（虽然合并排序与堆排序的时间复杂度量级相同，但一般还是比快速排序慢常数倍）。快速排序的算法核心与合并排序类似，也采用“分而治之”的想法：随机选定一个元素作为轴值，利用该轴值将数组分为左右两部分，左边元素都比轴值小，右边元素都比轴值大，但它们不是完全排序的。在此基础上，分别对左右两部分递归调用快速排序，使得左右部分完全排序。算法的平均时间复杂度是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较小的情况。空间复杂度也为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），直至所有文件块读取完毕。
本文节选自《程序员面试白皮书》
本书是程序员和IT从业人员的面试求职指南。本书遵从大多数面试参考图书的组织方式，结合实例，按照常见的数据结构、算法以及计算机基础知识进行章节划分。每一章的“知识要点”部分介绍章节涉及的相关知识点，回顾重要的基础知识点；“模式识别”部分给出一些例题，帮助大家总结解决相关问题的常见方法，并且通过分析问题中的关键信息，教授读者如何从题目中分析题型和解题方法。程序员面试是对于面试者计算机知识的全面检测，因此，本书设有专门的章节覆盖了网络、操作系统、编译器、算法和数据结构等等各个领域的知识。
本书作者来自硅谷一线的IT公司，书中包含了作者亲身的经验和体验，书中收集的题目部分来自互联网上分享的面试经验、在线编程网站leetcode，以及一些著名的面试参考资料。本书适合想要从事正规的程序员、架构师以及相关IT公司的专业人士和学生参考，尤其适合那些以一线IT外企或互联网公司为求职目标的读者阅读。