所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
本文对八种常见的排序算法进行原理分析、代码实现和效率分析，并对一些排序算法进行优化。本文对排序的分析均以整型、升序排序为例。
排序的相关概念
排序的稳定性
排序的稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序和外部排序
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
插入排序
插入排序的基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
直接插入排序
原理分析
当插入第 i (i>=1) 个元素时，前面的 array[0],array[1],…,array[i-1] 已经排好序，此时用 array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移。
代码实现
void InsertSort(int* a, int n)
{
for (int i = 1; i < n; i++)
{
int end = i - 1; //有序部分的边界
int tmp = a[i]; //待插入数据
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else {
break;
}
}
a[end + 1] = tmp;
}
}效率分析
时间复杂度：O(N2) 数组越接近有序插入排序效率越高，当数组已经有序时，时间复杂度为O(N)；当数组倒序时为最坏情况，此时时间复杂度为O(N2)。
空间复杂度：O(1)
稳定性：稳定
希尔排序
原理分析
希尔排序又称缩小增量排序。希尔排序法的基本思想是：现将待排序序列穿插分成 gap 组，所有距离为 gap 的元素分在同一组内，并对每一组的元素进行排序。然后不断缩小 gap，当gap为 1 时，所有组在序列内有序。
当 gap > 1 时进行的是预排序，目的是让序列更快接近有序；当gap == 1时，进行的是直接插入排序，此时序列已经很接近有序了，所以效率就会很高。希尔排序通过预排序使算法的整体效率得到提升。
代码实现
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1; //缩小gap
for (int i = gap; i < n; i++)
{
int end = i - gap;
int tmp = a[i];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else {
break;
}
}
a[end + gap] = tmp;
}
}
}效率分析
希尔排序的时间复杂度计算十分复杂，这里只给出定性的分析。组距为 gap 时，序列被分为 gap 组，每组的元素个数为 n/gap，当 gap 很大时（假设gap初始为 n/3），序列被分为 n/3 组，每组的元素个数为 3，对每组的排序消耗可以认为是一个常数时间，故开始时的排序消耗可以认为是线性时间O(N)；当 gap 很小时，此时序列已经接近有序，此时分别对每组的排序消耗也可以认为是线性时间。对 gap 的缩小过程消耗时间为O(logN)，故可以认为希尔排序的时间复杂度为O(N*logN)。
若尝试用某一序列实例对上述过程进行具体计算，可以发现分别对每组排序的时间消耗是一个以O(N)为下界的先增后减的过程。有人在大量的实验基础上推出：当元素个数 n 在某个特定范围内，希尔排序所需的移动和比较次数大约为n1.3；在《计算机程序设计技巧》中，Knuth利用大量的实验资料得出，当 n 很大时，元素平均比较次数和对象平均移动次数大约在n1.25到1.6*n1.25之间。
空间复杂度：O(1)
稳定性：不稳定
选择排序
选择排序的基本思想是：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列待排序部分的起始位置，直到全部待排序的数据元素排完。
直接选择排序
原理分析
- 在元素集合 array[i]--array[n-1] 中选择关键码最大(小)的数据元素
- 若它不是未排序序列元素中的最后一个(第一个)元素，则将它与未排序序列元素中的最后一个（第一个）元素交换
- 在剩余的 array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余 1 个元素，此时序列有序。
代码实现
为了尽可能提高直接选择排序的效率，这里一次从序列中选出最大值和最小值，分别与序列最后一个和第一个元素交换。此时需要注意的是，最大元素位置 maxi 和序列第一个元素位置可能重合，此时进行第一次交换后要对 maxi进行修正。
void SelectSort(int* a, int n)
{
int left = 0;
int right = n - 1;
while (left < right)
{
int mini = left;
int maxi = left;
for (int i = left; i <= right; i++)
{
mini = a[i] < a[mini] ? i : mini;
maxi = a[i] > a[maxi] ? i : maxi;
}
Swap(a + mini, a + left);
if (maxi == left) {
maxi = mini;
}
Swap(a + maxi, a + right);
left++;
right--;
}
}效率分析
时间复杂度：O(N2)
空间复杂度：O(1)
稳定性：不稳定
堆排序
原理分析
堆排序 (Heapsort) 是利用优先队列(堆)的一种排序算法，它利用堆的堆序性质快速选择出最大或最小的数据，以实现对序列的排序。关于堆排序的具体过程，请参考堆的分析和应用。
代码实现
void AdjustDown(int* a, int n, int root)
{
int parent = root;
int child = parent * 2 + 1;
while (child < n)
{
if ((child + 1 < n) && (a[child + 1] > a[child])) {
child++;
}
if (a[parent] < a[child])
{
Swap(a + parent, a + child);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
void HeapSort(int* a, int n)
{
for (int i = (n - 2) / 2; i >= 0; i--)
{
AdjustDown(a, n, i); //向下调整建堆
}
int end = n - 1;
while (end > 0)
{
Swap(a + 0, a + end);
AdjustDown(a, end, 0);
end--;
}
}效率分析
堆的时间复杂度为 O(N*logN) ，关于这个时间复杂度的具体计算，请参考堆的分析和应用。
空间复杂度：O(1)
稳定性：不稳定
交换排序
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
冒泡排序
原理分析
对序列中两个相邻的元素进行比较，若后一个元素比前一个元素小，则将两个元素交换，重复此过程，冒泡排序会不断将大的元素移动到后面位置。每趟冒泡排序会选出当前序列未排序部分的最大值。
通过对本趟冒泡排序的交换情况做一个判断，可以提前终止排序，以提高序列基本有序时排序的效率。
代码实现
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n - 1; j++)
{
bool exchange = false;
for (int i = 1; i < n - j; i++)
{
if (a[i - 1] > a[i]) {
Swap(a + i - 1, a + i);
exchange = true;
}
}
//该趟排序未交换，说明序列已经有序
if (!exchange) {
break;
}
}
}效率分析
时间复杂度：O(N2)；当序列已经有序时，时间复杂度为O(N)
空间复杂度：O(1)
稳定性：稳定
快速排序
基本思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值(key)，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
实现方法
当我们在讨论快速排序的实现时，讨论的其实是对单趟的排序以及对各个区间的排序。
快速排序单趟排序的方法主要有Horare的原始方法、挖坑法和双指针法，三种方法的目的都是将基准值置于序列有序后的位置。下面对快排的实现都取序列第一个元素作为基准值。
Horare版本
Horare版本的具体实现为：将序列第一个元素作为基准值key，以序列第一个元素作为左指针left，以序列最后一个元素作为右指针right，右指针先向左找严格小于key的元素，找到后，左指针向右寻找严格大于key的元素，交换left和right指针指向的元素，直至left与right相遇，此时相遇位置的元素一定严格小于key，交换key和相遇点的元素，此时key即位于序列有序后的所在位置。
需要注意的是，若将序列第一个元素作为key，必须使right指针先移动，此时left与right的相遇位置的元素才会一定严格小于key；同样的，若将序列最后一个元素作为key，必须先使left指针先移动，此时left与right的相遇位置才会一定严格大于key。下面给出逻辑证明：
left与right指针移动，相遇只有两种情况：
- left指针遇到right指针(L->R)
- right指针遇到left指针(R->L)
L->R的情况为：right指针找到小于key的元素，left指针未找到大于key的元素，此时left指针与right指针相遇，该位置的元素一定严格小于key
R->L的情况为：right指针在某一轮未找到小于key的元素，此时right指针与left指针相遇，若left恰指向key，此时不做处理；若left不指向key，则经过上一轮的寻找和交换，此时left指向的元素一定严格小于key，即相遇点的元素一定严格小于key
综上，若将序列第一个元素作为key，必须使right指针先移动，此时left与right的相遇位置的元素一定严格小于key。
int PartSort1(int* a, int left, int right)
{
//三数取中
int midI = GetMIdI(a, left, right);
Swap(a + midI, a + left);
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi]) {
right--;
}
while (left < right && a[left] <= a[keyi]) {
left++;
}
Swap(a + left, a + right);
}
Swap(a + keyi, a + left);
keyi = left;
return keyi;
}
挖坑法
挖坑法的具体实现为：将第一个元素存储在临时变量key中，形成一个坑位pit，左指针left和右指针right分别指向第一个元素和最后一个元素，right指针先向左寻找严格小于key的元素，找到后将right位置的值放入坑位中，right位置形成新的坑位，然后left向右寻找严格大于key的元素，重复上述过程，直到left与right在坑位相遇，此时将key的值放入坑位，即可完成一趟排序。
int PartSort2(int* a, int left, int right)
{
int midI = GetMIdI(a, left, right);
Swap(a + midI, a + left);
int key = a[left];
int pit = left;
while (left < right)
{
while (left < right && a[right] >= key) {
right--;
}
a[pit] = a[right];
pit = right;
while (left < right && a[left] <= key) {
left++;
}
a[pit] = a[left];
pit = left;
}
a[pit] = key;
return pit;
}双指针法
双指针法的具体实现为：取指针cur和prev初始均指向第一个元素key：
- 若cur指向的元素严格小于key，则先prev++，prev指向的元素与cur指向的元素交换，然后cur++
- 若cur指向的元素大于等于key，则cur++
- 重复上述过程，直到cur完全遍历序列，此时将第一个元素与prev指向的元素交换，即可完成一趟快速排序
int PartSort3(int* a, int left, int right)
{
int midI = GetMIdI(a, left, right);
Swap(a + midI, a + left);
int cur = left;
int prev = left;
int keyi = left;
while (cur <= right)
{
if (a[cur] < a[keyi])
{
prev++;
Swap(a + prev, a + cur);
cur++;
}
else {
cur++;
}
}
Swap(a + keyi, a + prev);
keyi = prev;
return keyi;
}递归实现
对序列进行第一次单趟排序后，可以以keyi为中心，将序列划分为左、右两个区间，用递归的方式分别对左右区间进行排序，当左右区间都有序后，整个序列有序。
快速排序的递归实现类似于二叉树的前序遍历过程。
void QuickSort(int* a, int left, int right)
{
//只有一个元素或者区间不存在，不需要排序
if (left >= right) {
return;
}
//小区间优化
if (right - left + 1 > 10)
{
int keyi = PartSort3(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
else {
InsertSort(a + left, right - left + 1);
}
}非递归实现
快速排序整体也可以用栈实现。可以注意到，每趟快排只需要知道区间的左边界left和右边界right即可对该区间进行单趟排序，所以我们可以用栈记录区间的左右边界，进而模拟上文的递归过程。具体操作为，将整个序列的左右边界入栈后：
- 出栈顶的序列边界，对边界内的序列进行单趟排序，返回新的keyi值
- 以keyi值为中心将当前序列划分为左右两部分，将需要排序部分的序列边界入栈，因为栈具有FILO的性质，所以先入右边部分的序列，再入左边部分的序列
- 重复上述过程，直至栈为空
void QuickSortNonR(int* a, int left, int right)
{
Stack sT;
StackInit(&sT);
StackPush(&sT, right);
StackPush(&sT, left);
while (!StackEmpty(&sT))
{
int begin = StackTop(&sT);
StackPop(&sT);
int end = StackTop(&sT);
StackPop(&sT);
int keyi = PartSort2(a, begin, end);
//[begin, keyi - 1] keyi [keyi + 1, end]
//先入右区间，再入左区间
if (keyi + 1 < end)
{
StackPush(&sT, end);
StackPush(&sT, keyi + 1);
}
if (begin < keyi - 1)
{
StackPush(&sT, keyi - 1);
StackPush(&sT, begin);
}
}
StackDestroy(&sT);
}除了用栈模拟递归实现快排外，也可以用队列分别对每层序列进行排序。
优化
针对普通快排存在的问题，上面给出的代码已经进行优化，下面对这些优化进行讨论。
三数取中
可以注意到，在序列已经有序（升序或降序）时，快排的时间复杂度为O(N2)，这是因为在这种情况下，keyi的位置总是和序列边界重合，对序列整体的分区和排序过程其实是一个等差数列。
在理想情况下，keyi的位置在序列中间，此时将序列分区间时近似平分状态，可以使排序过程最类似二叉树结构以达到排序的理想效率。为了达到这一目的，我们的做法是三数取中：取left、right和序列中间位置mid指向元素中的中间值，将此中间值作为key。
int GetMidI(int* a, int left, int right)
{
int midI = (left + right) / 2;
if (a[left] < a[midI])
{
if (a[midI] < a[right]) {
return midI;
}
else if (a[midI < a[left]]) {
return left;
}
else {
return right;
}
}
else //a[left] >= a[mid]
{
if (a[midI] > a[right]) {
return midI;
}
else if (a[midI] > a[left]) {
return left;
}
else {
return right;
}
}
}小区间优化
对于很小的数组，插入排序的效率往往很高，所以我们考虑对于很小的区间不再进行递归，而采用插入排序。相对于单纯使用快速排序，这种方法可以大量节省递归空间，并可以节省大约15%的运行时间。
三路划分
在上面的快排中，我们选出一个key，经过一趟排序后将数组划分为了两个区间，key左边的数组均为小于等于key的数，key右边的数组均为大于等于key的数，这种方式成为两路划分。针对具有大量重复数据的数组，两路划分的时间复杂度趋于O(N2)，为了解决这个问题，引出三路划分的快速排序。
三路划分的基本思想是：将数组调整为三个区间 [begin, left - 1] 小于key值，[left, right] 等于key值，[right + 1, end] 大于key值，递归时只递归[begin, left - 1] 和 [right + 1, end]即可，中间区间不做处理。
具体操作为：
- 设指针left、right分别指向数组边界，cur指向第一个数据，判断cur指向的数据与key的大小关系；
- 若a[cur] < key，则交换cur和left指向的数据，left后移一位，cur后移一位；
- 若a[cur] == key，则cur后移一位；
- 若a[cur] > key，则交换cur和right指向的数据，right左移一位，cur不做处理。注意此时不要将cur右移，因为从right交换来的数据大小不确定，必须由下次循环进行判断和处理，此时cur的位置相当于一个中转。
- 重复上述步骤，直至cur > right时循环结束。
//三路划分 + 三数取中 + 小区间优化的快速排序
void QuickSort(int* a, int left, int right)
{
if (left >= right) {
return;
}
if ((right - left + 1) > 10)
{
int keyi = GetMidI(a, left, right);
Swap(a + left, a + keyi);
int key = a[left];
int begin = left;
int end = right;
int cur = left;
while (cur <= end)
{
if (a[cur] < key)
{
Swap(a + cur, a + begin);
cur++;
begin++;
}
else if (a[cur] > key)
{
Swap(a + cur, a + end);
end--;
}
else {
cur++;
}
}
//[left, begin - 1] [begin, end] [end + 1, right]
QuickSort(a, left, begin - 1);
QuickSort(a, end + 1, right);
}
else
{
InsertSort(a + left, right - left + 1);
}
}效率分析
若不考虑小区间优化，则快速排序的效率计算为：
