前言

排序算法大概是学习编程最早接触到的一类算法了，一段时间以来我一直依赖C++提供的标准库函数sort进行排序，基本没有手写过排序算法。刚好C语言课提到这个，干脆就总结并手写一下各大排序算法吧。

本文将会分别从算法原理、实现方法、时间空间复杂度分析和稳定性分析四个方面讨论各大排序算法。另外，我们默认将序列从小到大进行排序。

比较类排序

冒泡排序

冒泡排序（Bubble Sort）是一种十分简单的排序算法。它通过元素之间的两两比对，在每一趟排序的过程中，将最大的元素沉入序列尾部。容易得到，对于含有N个元素的序列，只需要进行N-1趟排序过程，便可将整个序列变为有序。

这样的算法实现了一个大元素不断下沉、小元素不断上浮的过程，从直观上看如同水里泡泡的沉浮，因而得名冒泡排序。

冒泡排序算法可被描述为以下几个步骤：

使用指针i指向最后一个沉入序列尾端的元素（初始时沉入序列尾端的元素为空，则i指向哨兵）
指针j从第一个元素开始，依次指向每一个元素，直至遇到i - 1所指向的元素为止
对于指针j指向的每一个元素，将其与j + 1所指向的元素进行大小比较，若指针j所指向的元素大于j + 1所指向的元素，则交换二者位置
重复执行1-3步，直至指针i指向第一个元素为止

void bubble_sort(int *array, int length)
{
    for(int i = length; i > 0; i--)
    {
        for(int j = 0; j < i - 1; j++)
        {
            if(array[j] > array[j + 1])
            {
                int temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
            }
        }
    }
}

我们可以对上述算法做一个小优化。通过观察可以发现，对于其中的某一趟排序，如果指针j从第一个元素依次指向到i - 1所指向的元素的过程中没有发生任何一次交换，则序列事实上已经有序，剩余的排序步骤便可以直接跳过了。我们只需要在每一趟排序的过程中维护一个变量flag，用以标志该趟排序是否发生了元素交换即可。

void bubble_sort(int *array, int length)
{
    for(int i = length; i > 0; i--)
    {
        int flag = 0;
        for(int j = 0; j < i - 1; j++)
        {
            if(array[j] > array[j + 1])
            {
                flag = 1;
                int temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
            }
        }
        if(!flag)
            break;
    }
}

我们考虑冒泡排序的时间复杂度。不难得到，当序列初始即有序时为最好的情况，只需将序列从头到尾扫描一遍，此时的时间复杂度为O(N)。当序列初始完全反序时为最差的情况，此时的时间复杂度为O(N^2)。算法的平均复杂度为O(N^2)。

由于只有当前一个元素严格大于后一个元素时，二者才会发生交换，所以冒泡排序算法是稳定的。

选择排序

选择排序（Selection Sort）也是一种常见的简单排序算法。它将整个序列划分为已排序区和未排序区，通过不断寻找未排序区的最小元素，将其放置到已排序区的尾端（与未排序区的第一个元素交换），直到未排序区的元素为空而实现序列的有序化。

不断寻找未排序区的最小元素这一操作，换言之就是在未排序区选择一个最小元素，因而得名选择排序。

选择排序算法可被描述为以下几个步骤：

使用指针i指向未排序区的第一个元素（初始时整个序列为未排序区，i指向首元素）
使用变量minN保存未排序区的最小元素（初始值为未排序区的第一个元素，即指针i所指向的元素），变量index保存最小元素所在的数组下标
指针j从指针i + 1指向的元素开始，依次指向未排序区的每一个元素，对于指向的每一个元素，若其小于变量minN中所保存的元素，则更新变量minN中所保存的元素为该元素，变量index中所保存的元素下标为该元素下标
将指针i所指向的元素与指针index所指向的元素进行交换，此时已排序区的元素数量加一，未排序区的元素数量减一
重复执行1-4步骤，直至指针i指向序列的最后一个元素为止

void selection_sort(int *array, int length)
{
    for(int i = 0; i < length; i++)
    {
        int minN = array[i];
        int index = i;
        for(int j = i + 1; j < length; j++)
        {
            if(array[j] < minN)
            {
                minN = array[j];
                index = j;
            }
        }
        int temp = array[i];
        array[i] = minN;
        array[index] = temp;
    }
}

我们考虑选择排序的时间复杂度，不难发现，无论序列如何，总需要扫描N*N遍序列，因此它的时间复杂度总为O(N^2)。

对于两个相邻的相等元素，当前者处于未排序区的首元素时，若后面能够选择到更小的元素，则该元素会直接与其进行交换，从而改变两个相等元素的初始顺序。因此，选择排序算法是不稳定的。

插入排序

插入排序（Insertion Sort）也是一种简单排序算法。插入排序算法的执行过程中，对于每一个元素，位于其之前的所有元素所构成的序列是有序的（对于首元素，我们认为其已经有序）。因此，它从序列的首元素开始扫描，对于每一个元素，找到它位于已有序序列的正确位置，然后直接插入，使得插入后该有序序列仍然有序。

这种类似对扑克牌手牌进行排序的插入操作过程，就是插入排序的得名原因。

插入排序算法可被描述为以下几个步骤：

指针i从序列的第二个元素开始，依次指向每一个待插入的元素，对于每一个元素执行2-4步骤
使用变量temp保存指针i所指向的元素
指针j从指针i - 1所指向的元素开始，从后往前扫描，对于每一个元素，若其大于变量temp所保存的元素，则将该元素往后挪动一个位置；若其小于等于变量temp所保存的元素，则扫描停止
将变量temp所保存的元素插入到指针j + 1所指向的元素位置

void insertion_sort(int *array, int length)
{
    for (int i = 1; i < length; i++)
    {
        int temp = array[i];
        int j = i - 1;
        for (; j >= 0 && array[j] > temp; j--)
        {
            array[j + 1] = array[j];
        }
        array[j + 1] = temp;
    }
}

我们考虑插入排序的时间复杂度，显然，和冒泡排序一样，最好的情况是初始序列已经有序，此时只需要完整扫描一遍序列即可，时间复杂度为O(N)；最差的情况为序列倒序，此时的时间复杂度为O(N^2)；平均时间复杂度为O(N^2)。

由于只有当被比较元素严格大于待插入元素时，其位置才会向后挪动一位，使得待插入元素的位置处于其之前，故对于两个相邻的相等元素，在排序过程中后者不会插入至前者之前。因此，插入排序算法的稳定的。

希尔排序

希尔排序（Shell Sort）是对插入排序的改进，又称“缩小增量排序”（Diminishing Increment Sort）。它选择一个数作为增量，然后将整个序列分为若干个子序列（子序列中每个元素下标之间的差值等于增量），对每个子序列进行插入排序。接着减小增量的值，重新划分子序列，再次进行插入排序。重复执行操作，直到增量值为1，进行最后一次插入排序，便可完成整个序列的排序。

我们知道，插入排序的最好时间复杂度为O(N)，最差时间复杂度为O(N^2)，与冒泡排序的时间复杂度一致，他们都是基于相邻元素两两比较的算法。事实上，我们还可以将该结论推广至其他基于这种比较原理的算法。

基于相邻元素两两比较的算法在每次操作中最多只能消去一个逆序对，因此逆序对的个数决定了排序算法的执行次数。而对于由N个不同元素所组成的任意序列而言，其平均具有N(N - 1)/4个逆序对（数量级为N^2）。这意味着，任何基于相邻元素两两比较的算法，其平均时间复杂度总在O(N^2)之下而无法超越它。

基于此，为了让插入排序的时间复杂度能够超过O(N^2)，我们需要让各元素能够跨越一定的距离进行比较，这样就使得通过一次交换而消除多对逆序对的情况成为可能，从而提高算法的效率。这就是希尔排序算法的设计原理。

希尔排序算法可被描述为以下几个步骤：

确定增量序列的表达式，使用变量d保存当前增量值
令指针i从数组下标为d的元素开始，依次指向每一个待插入的元素
使用变量temp保存指针i所指向的元素
指针j从指针i - d所指向的元素开始，从后往前扫描（每次向前移动d个位置），对于每一个元素，所其大于变量temp所保存的元素，则将其向后挪动d个位置；若其小于等于变量temp所保存的元素，则扫描停止
将变量temp所保存的元素插入到指针j + d所指向的元素位置
减小增量值d，重复执行2-5步骤。直到当增量值为1时，再次执行2-5步骤后停止

可以看到，希尔排序每次对增量值为d的子序列进行了插入排序。值得注意的是，尽管我们在逻辑中认为我们需要分别对各子序列进行排序，但在实际情况中，各子序列的排序是交替着进行的。当指针i指向哨兵时，所有的子序列都已排序完成。

原始希尔排序算法的C语言代码如下：

void shell_sort(int *array, int length)
{
    for(int d = length / 2; d > 0; d /= 2)
    {
        for(int i = d; i < length; i++)
        {
            int temp = array[d];
            int j = i - d;
            for(; j >= 0 && array[j] > temp; j -= d)
            {
                array[j + d] = array[j];
            }
            array[j + d] = temp;
        }
    }
}

原始希尔排序采用的增量序列为N/k, k∈{2, 4, 8, ... , 2^n}，这一增量序列可以使得希尔排序的平均时间复杂度达到O(N^1.3)。除了这一增量序列外，还有其他人提出的能够提高希尔排序算法时间复杂度的增量序列。但对采用不同增量序列的希尔排序算法的时间复杂度进行分析是十分复杂的，以致于其中一些增量序列甚至还只是猜想。

由于子序列排序过程是分别进行的，无法保证两个相邻的相等元素在最终的序列中顺序不发生改变。因此，希尔排序算法是不稳定的。

归并排序

归并排序（Merge Sort）算法是分治思想的典型应用。它将一个序列分为元素个数尽可能相等的两部分，再对这两部分子序列分别进行排序，最后，将排序好的两部分子序列合并为一个结果序列，从而完成排序。

归并排序因子序列的合并操作而得名。

归并排序的关键在于如何将两个有序的子序列合并为一个结果序列（对两部分子序列分别排序的问题通过递归即可解决）。不难得到，只需要不断地对比两个子序列首元素的大小，将其中较小的元素取出，放入结果数组，就可以完成合并。

需要注意的是，当其中一个子序列为空时，则无需比较大小，只需将另一子序列的所有元素导入结果序列即可。

归并排序算法的步骤描述与原理描述几乎一致，因此，下面直接给出归并排序的C语言实现：

void merge_sort(int *array, int left, int right, int *T)
{
    if(right - left <= 1)
        return;
    int mid = left + (right - left) / 2;
    merge_sort(array, left, mid, T);
    merge_sort(array, mid, right, T);
    int left_part = left, right_part = mid, index = left;
    while(left_part < mid || right_part < right)
    {
        if(right_part >= right || (left_part < mid && array[left_part] <= array[right_part]))
            T[index++] = array[left_part++];
        else
            T[index++] = array[right_part++];
    }
    for(int i = left; i < right; i++)
        array[i] = T[i];
}

由于采用了分治法，无论序列如何，归并排序算法的时间复杂度总为O(NlogN)。比起选择排序算法总为O(N^2)的时间复杂度，要好上很多了。但由于需要额外新的空间存放结果序列，其额外空间复杂度为O(N)。（上述介绍的所有排序算法的额外空间复杂度均为O(1)）

合并时若左序列首元素等于右序列首元素，则优先取出左序列的首元素存放至结果序列。因此，归并排序算法是稳定的。

快速排序

快速排序是最快的通用内部排序算法。

我写失败了，回头看会书再填坑

堆排序

树结构没有学会，暂时还写不了堆排序，待以后填坑

~~以后也不一定有时间填坑~~

非比较排序

计数排序

计数排序（Count Sort）是一种不基于元素对比的排序算法。对于一个元素最大值为maxValue的序列，计数排序算法维护了一个长度为maxValue + 1的内部数组。它从头到尾遍历序列中的每一个元素，将该元素在序列中出现的次数统计存放在以该元素值为下标的内部数组中。统计结束后，根据内部数组的下标及其存放的值即可导出排序后的序列。

该算法的实现较简单，下面直接给出其C语言实现：

void count_sort(int *array, int length)
{
    int maxValue = 0;
    for (int i = 0; i < length; i++)
        maxValue = (array[i] > maxValue) ? array[i] : maxValue;
    int bucket[maxValue + 1];
    int index = 0;
    memset(bucket, 0, sizeof(bucket));
    for (int i = 0; i < length; i++)
        bucket[array[i]]++;
    for (int i = 0; i < maxValue + 1; i++)
    {
        while (bucket[i])
        {
            array[index++] = i;
            bucket[i]--;
        }
    }
}

可见，这是一种以空间换时间的排序算法，只需要分别遍历一遍序列与内部数组就可以得到结果，因此可以认为其时间复杂度为O(n)。这一时间复杂度要好于任何一种比较类排序算法。

然而，计数排序算法并非通用排序算法，其使用具有一定的约束条件。首先，由于数组的下标只能为正整数，计数排序只能解决正整数序列的排序问题；其次，由于栈内存的大小限制，当正整数非常大的时候，计数排序也无法进行解决。

计数排序算法是稳定的。

基数排序

基数排序（Radix Sort）与计数排序的原理相同，均是利用键值对，以空间换时间提高排序效率。不同的是，基数排序将正整数按位数进行拆分，从最低位开始，采用计数排序算法进行排序，直至最高位排序完毕，所有正整数的排序也就完成了。

累了累了，下次再填坑

桶排序

好累啊，不想写了，下次再填坑吧

尾声

排序算法作为编程入门接触的第一类算法，无疑是一道不小的坎。尽管在实际应用中往往并不会遇到需要手写排序算法的场景，因为几乎所有的编程语言，其库函数都已提供了高效的排序算法（C语言也不例外）。但了解这些排序算法的基本原理与优化思路（例如归并和快排的分治思想），却很好地训练编程思想与解题思维。

原想着开坑就写完十大经典排序算法，却没想到一些排序算法由于从未手写过，实际上写起来还是蛮磕磕碰碰的；以及涉及到数据结构的堆排序，也并没能直接写出来。

编程还是得多实践啊。

ACM的入门题还没肝完，这周博文的坑就留到下周填吧orz