数据结构07-排序算法

数据结构与算法 2022年9月9日

本节暂时不讨论数据结构，而是研究算法。排序(sort)是一个经典的算法问题，有许多算法都可以用于排序，但是它们各有优缺点。本节讨论各种排序算法并分析其特点。

为了方便起见，本节介绍的排序算法都用于将数组内的元素排序，只要知道其原理就可以将其应用到其余需要的数据结构中。排序的依据是元素的大小。也就是说两个元素可以直接做比较。

排序算法

选择排序

选择排序(selection sort)应该是最易于理解的排序算法，早在第一节中就已经介绍过其原理，这里再次重复一遍：先找出数组的最小元素并移动到数组的起始位置，然后每次都从剩余未排序元素中选择最小元素并放到已排序序列的末尾，直到没有待排序元素为止。

根据以上介绍，选择排序的代码实现如下：

void SelectionSort(int arr[], int len) {
    int min;
    for (int i = 0; i < len - 1; i++) {
        min = i;
        for (int j = i + 1; j < len; j++)
            if (arr[j] < arr[min])
                min = j;
        array_swap(arr, min, i);
    }
}

选择排序是一个典型的时间复杂度为 \\( O(N^2) \\) 的排序算法，因为代码中有两层嵌套的循环，每层循环的次数都与 \\( N \\) 有关，并且循环不会中断。

从原理上理解，不管原始数组如何，代码都需要花费线性时间找出数组的最小值，然后又花费线性时间找出数组的次小值，一共有线性个元素需要寻找，因此时间复杂度为 \\( O(N^2) \\) 。

这种排序算法平平无奇，很难有改进的余地，接下来再看一个同样简单的排序算法：插入排序。

插入排序

插入排序(insertion sort)同样是一种简单的排序算法，其原理是：顺序扫描整个数组，将扫描的每个元素依次插入已排序序列的适当位置。

插入排序的代码实现为：

void InsertionSort(elemtype arr[], int len) {
    for (int i = 0; i < len; i++) {
        elemtype temp = arr[i];
        int j;
        for (j = i; j > 0 && arr[j - 1] > temp; j--)
            arr[j] = arr[j - 1];
        arr[j] = temp;
    }
}

插入排序也有两层嵌套的循环，且每层循环也和 \\( N \\) 有关。但是内层循环是可能终止的：如果待排序元素比已排序序列末尾（最大）的元素还大，那么它就无需移动，放在原位就可以作为已排序序列的一部分，这就避免了插入时需要找到合适位置的线性复杂度。

在极端情况下，如果一个数组本身就是有序的，那么顺序扫描整个数组时，程序会发现数组与之前的序列总是能直接构成有序序列，这样每一个元素都无需移动，时间复杂度可以达到 \\( O(N) \\) 。

如果原始数组越有序，那么无需移动的元素个数也越多，排序需要花费的时间也越短。在平均情况下，如果数组完全是随机的，那么显然需要移动的元素个数随着数组的大小线性增长，而移动又要花费线性时间，因此插入排序的平均时间复杂度仍然为 \\( O(N^2) \\) 。

希尔排序

希尔排序(Shell sort)是最早突破二次时间屏障的算法之一，它利用了插入排序在数组偏向有序时效率会更高的特点。

希尔排序使用一个增量序列(increment sequence) \\( h_1, h_2, \dots, h_t \\) ，在使用 \\( h_k \\) 做一次排序之后，数组中所有相隔为 \\( h_k \\) 的元素都被排序。也就是说，将 \\( h_k, h_k + 1, \dots, N-1 \\) 每个位置的元素使用插入排序放到 \\( i, i-h_k, i-2h_k, \dots \\) 中的正确位置上。

提出者 Donald Shell 建议的增量序列的选择为：

\\[ h_1 = \lfloor N / 2 \rfloor \\ h_{k+1} = \lfloor h_k / 2 \rfloor \\]

该增量并不是效率最高的增量，但是比较流行。使用该增量编写的希尔排序如下：

void ShellSort(elemtype arr[], int len) {
    for (int inc = len / 2; inc > 0; inc /= 2)
        for (int i = inc; i < len; i++) {
            elemtype temp = arr[i];
            int j;
            for (j = i; j >= inc; j -= inc)
                if (temp < arr[j - inc])
                    arr[j] = arr[j - inc];
                else
                    break;
            arr[j] = temp;
        }
}

有了以上函数，就可以分析其复杂度了。虽然以上函数有三层嵌套循环，但并不意味着时间复杂度就为三次函数。希尔排序在条件最差的情况下，其时间复杂度为 \\( O(N^2) \\) 。

在增量为 \\( h_k \\) 时，需要有 \\( h_k \\) 组，每组 \\( N / h_k \\) 个元素做插入排序。假设这些插入排序都是平均或最坏情况的二次时间，那么该增量下排序的总时间花费为：

\\[ O(h_k \dot (N/h_k)^2) = O(N^2/h_k) \\]

对所有增量下排序的时间总和为：

\\[ O(\sum_{i=1}^{t}N^2/h_i)=O(N^2\sum_{i=1}^{t} 1/h_i) \\]

由于 \\( h_t \\) 的取值为 1 ，其余值应该大于前一个值的两倍，因此该数列是一个等比数列，总和小于 2 ，故时间复杂度为 \\( O(N^2) \\) 。

希尔排序的时间复杂度是一个复杂的问题，甚至许多增量下平均情况的时间复杂度都还没解决。目前还不能确定取什么增量具有最好的时间复杂度，不过它确实有优于二次函数的时间复杂度：当增量序列取用 \\( 2^k-1, \dots, 7, 3, 1 \\) 时，其时间复杂度为 \\( O(N^{3/2}) \\) ，不过证明该结论需要一定数论知识。

还有许多不同的增量序列可供选取，例如 \\( 2^{k-1} + 1, \dots, 9, 5, 3, 2, 1 \\) 或 \\( 0.5(3^{k-1}-1), \dots, 40, 13, 4, 1 \\) 等。在选取增量序列时需要注意序列的最后一个值需要为 1 ，使数组最终要让所有元素都一起参与排序；并且序列中的值不要有除 1 以外的其它公因数，否则这些位置上的值会多次一并参与排序，影响效率。

堆排序

在上一节 中介绍了堆的概念。二叉堆能以 \\( O(1) \\) 的时间做插入，并以 \\( O(\log N) \\) 的时间删除最小值。

删除是有序的，因此可以借由该性质完成排序：如果将数组内的每个元素插入二叉堆中，然后再按值的大小顺序出队，那么就可以得到一个有序的结果。

单个插入需要 \\( O(1) \\) 的时间，插入所有元素就需要 \\( O(N) \\) 的时间。删除最小值并放到数组中的合适位置需要花费 \\( O(\log N) \\) 的时间，将所有元素依次删除就需要花费 \\( O(N\log N) \\) 的时间。两者是先后执行的关系，总的时间复杂度也是二者之和，因此总的时间复杂度为 \\( O(N\log N) \\) 。

这是目前为止效率最好的排序算法，不过它需要一个额外的数组来构建二叉树，因此需要 \\( O(N) \\) 的空间复杂度。

可以对二叉堆做一定调整来避免额外的线性空间要求：注意到二叉堆在删除一个元素时，堆的最后一个元素空缺了出来，并且随着删除的继续，数组从后向前腾出空间。如果将每次删除的元素放在因删除而空缺出的位置上，就可以利用单个数组构建二叉堆并排序为数组。

不过这样得到的最终数组后面位置的元素小而前面位置的元素大。如果想得到升序排列的数组，可以对二叉堆做一定改进，使其每次在删除时，删除的是最大的元素而不是最小的元素。

这种堆称为 max-堆。它的堆序性质与上一节介绍的二叉堆是相反的：大的元素在上，小的元素在下。下图展示了一个 max-堆的结构：

除此之外，max-堆的操作思路都与普通的二叉堆相同。例如，可以将堆中的任意一个元素调整到合适的位置上：

#define leftchild(pos) (2 * (pos) + 1)

static void PercolateDown(elemtype arr[], int len, int pos) {
    int child;
    elemtype temp;
    for (temp = arr[pos]; leftchild(pos) < len; pos = child) {
        child = leftchild(pos);
        if (child != len - 1 && arr[child + 1] > arr[child])
            child++;
        if (temp < arr[child])
            arr[pos] = arr[child];
        else
            break;
    }
    arr[pos] = temp;
}

注意：使用堆对数组排序时，索引值为 0 的位置上是有元素的，因此左子节点的计算方式略有不同。

堆的构建与删除都是基于该基本操作实现的：

void HeapSort(elemtype arr[], int len) {
    for (int i = len / 2; i >= 0; i--)
        PercolateDown(arr, len, i); // build heap
    for (int i = len - 1; i > 0; i--) {
        array_swap(arr, 0, i);      // delete max
        PercolateDown(arr, i, 0);
    }
}

在构建堆时，只需要将前半个数组的元素调整到合适的高度上，后半个数组的元素会在此过程中自动调整，且它们没有子节点，无需做进一步的调整。

归并排序

归并排序(merge sort)同样是一种很快的排序算法。它的基本思想是合并：如果给定两个已排序的子数组，如果要将其合并为一个数组，只需要顺序遍历两个数组，不断将较小值放入合并数组的下一个位置即可。

假设要将一个数组的左右两部分合并成一个完整的数组：

那么合并的代码实现如下：

static void Merge(elemtype arr[], elemtype temp[],
                  int left, int right, int end) {
    int leftend = right - 1;
    int elems = end - left + 1;
    int curpos = left;

    while(left <= leftend && right <= end)
        if (arr[left] <= arr[ right ])
            temp[curpos++] = arr[left++];
        else
            temp[curpos++] = arr[right++];

    while (left <= leftend) // Copy rest of first half
        temp[curpos++] = arr[left++];
    while (right <= end)    // Copy rest of second half
        temp[curpos++] = arr[right++];

    for (int i = 0; i < elems; i++, end--)
        arr[end] = temp[end];  // Copy temp back
}

程序中需要考虑处理完一个数组的情况，此时只需要将另一个数组剩余的部分全部拼接到合并数组的末尾即可。

归并排序很适合使用递归的方式解决：只需要一开始将每个元素都看作一个有序的子数组，然后不断对有序的子数组之间两两合并，就可以逐渐将小数组合并为大数组，直至合并为一个完整的有序数组。

递归实现下，使用代码描述非常简单：

void _MergeSort(elemtype arr[], elemtype temp[], int left, int right) {
    if (left < right) {
        int center = (left + right) / 2;
        _MergeSort(arr, temp, left, center);
        _MergeSort(arr, temp, center + 1, right);
        Merge(arr, temp, left, center + 1, right);
    }
}

先将待排序数组尽量均分，然后递归地对这两部分实施归并排序，最后再将两个排序完成的子数组合并起来。

该函数一般不用于直接执行，还需要一个入口函数驱动它：

void MergeSort(elemtype arr[], int len) {
    elemtype* temp = malloc(sizeof(elemtype) * len);
    if (temp) {
        _MergeSort(arr, temp, 0, len - 1);
        free(temp);
    }
}

从直观上看，每一次合并主要花费的时间在于顺序遍历数组，因此对数组做一次（影响每个元素的）排序并合并需要花费线性时间。第一次排序可以将单独元素的数组合并为两个元素的数组，第二次合并将两个元素的数组合并为 4 个元素的数组，那么最终经过对数次数的合并，就可以将其合并为包含所有元素的数组，因此归并排序的时间复杂度为 \\( O(N \log N) \\) 。

此外，归并排序必须使用一个辅助数组用于存储排序的中间结果。不过需要的额外空间不会超过原始数组大小，因此归并排序的空间复杂度为 \\( O(N) \\) 。

快速排序

和它的名字一样，快速排序(quick sort)速度很快。快速排序的思想是首先从数列中随机选出一个元素作为枢纽元(pivot)，将比枢纽元大的元素放在它的左端，将比枢纽元小的元素放在它的右端，此时枢纽元就相对它的左右端有序，再递归地将左端和右端按这种方式排序即可。

归并排序将小数组合并为大数组，而快速排序将大数组分割为小数组再互相排序。当数组足够小（如元素个数小于等于 3 个）时已经无需划分，可以使用其余比较简单的排序方式（如插入排序）即可。

枢纽元的选取非常重要，因为它应该能反映一个比较中间的位置，如果选取的是数组内元素的最值，那么它将花费线性的时间将其它元素都移到它的同一边，且一次只能将一个元素排到合适的位置，使快速排序达到最坏的情况 \\( O(N^2) \\) 。

一个比较合理且速度较快的方法是三数中值分割法(median-of-three partitioning)，即随机选取三个数并取用它们的中值。不过一般不会随机选取，而是取用数组的首端、末端和中间端的元素，再取它们的中值。三数中值分割法的代码实现如下：

static elemtype Median3(elemtype arr[], int left, int right) {
    int center = (left + right) / 2;
    if (arr[left] > arr[center])
        array_swap(arr, left, center);
    if (arr[left] > arr[right])
        array_swap(arr, left, right);
    if (arr[center] > arr[right])
        array_swap(arr, center, right);
    array_swap(arr, center, right - 1);  // hide pivot
    return arr[right - 1];               // return pivot
}

以上在寻找中值时将涉及到的元素放在合适的位置，方便后续程序处理。

快速排序的主要实现如下：

#define QUICKSORT_CUTOFF (3)

static void _QuickSort(elemtype arr[], int left, int right) {
    if (left + QUICKSORT_CUTOFF <= right) {
        elemtype pivot = Median3(arr, left, right);
        int i = left;
        int j = right - 1;
        while (1) {
            while (arr[++i] < pivot) continue;
            while (arr[--j] > pivot) continue;
            if (i < j)
                array_swap(arr, i, j);
            else
                break;
        }
        array_swap(arr, i, right - 1);  // restore pivot
        _QuickSort(arr, left, i - 1);
        _QuickSort(arr, i + 1, right);
    }
    else  // do an insertion sort on the subarray
        InsertionSort(arr + left, right - left + 1);
}

每一趟排序中，程序从左右两边向中间扫描，并将左边较大的元素和右边较小的元素交换位置，两边交汇的位置即为枢纽元应该位于的中值位置，该位置左边的元素都比枢纽元小，右边的元素都比枢纽元大。由于在寻找枢纽元时将其移动到了数组的末端，因此最后一步需要将其移动到合适的位置。

每一趟排序涉及数组内的每一个元素，因此需要花费线性时间；平均上看来，第一次排序将一个元素放在合适的位置，并分割为左右两端的子数组再排序，而下一次排序又将左右两端的子数组的各一个元素放在合适的位置，并再次分割为四个子数组。由此可见平均情况下已排序的元素将随着每趟排序指数增长，总的时间是两者之积 \\( O(N\log N) \\) 。

尽管时间复杂度都是 \\( O(N\log N) \\) ，但快速排序在多数情况下比堆排序和归并排序快。这是由于快速排序在每趟排序中，基本上只有一半左右的元素需要移动，而归并排序在每趟排序时每个元素都需要参与合并的移动；堆排序在插入和删除时也涉及所有元素的移动，因此它们的操作都比快速排序复杂，使得函数的常数项比快速排序大，相对来说运行的时间没有快速排序快。

最后，总结一下本节涉及到的所有排序算法的特点：

排序算法 最好运行时间 平均运行时间 最坏运行时间 额外空间需求
选择排序 \\( O(N^2) \\) \\( O(N^2) \\) \\( O(N^2) \\) \\( O(1) \\)
插入排序 \\( O(N) \\) \\( O(N^2) \\) \\( O(N^2) \\) \\( O(1) \\)
希尔排序 \\( O(N) \\) \\( O(N^{5/4}) \\)（与增量选取有关） \\( O(N^{3/2}) \\)（与增量选取有关） \\( O(1) \\)
堆排序 \\( O(N\log N) \\) \\( O(N\log N) \\) \\( O(N\log N) \\) \\( O(1) \\)
归并排序 \\( O(N\log N) \\) \\( O(N\log N) \\) \\( O(N\log N) \\) \\( O(N) \\)
快速排序 \\( O(N\log N) \\) \\( O(N\log N) \\) \\( O(N^2) \\) \\( O(1) \\)

排序算法有非常多种，本节只介绍了其中几个比较典型的排序算法。堆排序将数据结构二叉堆的性质应用在算法之中，建立了数据结构与算法之间的联系。

归并排序和快速排序是一种典型的分治(divide-and-conquer)算法：它将一个大的问题（数组排序）分成一系列较小的问题（数组的一部分排序），再将得到的各个部分合并为一个完整的答案，因此分治问题非常适合使用递归来实现。

近期文章

归档

京ICP备2021034974号
contact me by hello@frozencandles.fun