######################################## 排序 ######################################## 排序算法总结 **************************************** 排序算法可以分为以下几类： .. mermaid:: graph LR 插入排序 --> 直接插入排序 & 希尔排序 选择排序 --> 直接选择排序 & 堆排序 交换排序 --> 冒泡排序 & 快速排序 归并排序 计数排序 基数排序 +----------+-----------------+-----------------+------------------------------------------+-----------------+--------------------+-------------------+--------+--------+-------------------------------+ | 排序算法 | 平均时间复杂度 | 最优时间复杂度 | 最优场景 | 最差时间复杂度 | 最差场景 | 空间复杂度 | 原址性 | 稳定 | 适用场景 | +==========+=================+=================+==========================================+=================+====================+===================+========+========+===============================+ | 冒泡排序 | :math:`O(n^2)` | :math:`O(n)` | 数据完全有序 | :math:`O(n^2)` | | :math:`O(1)` | | 是 | 数据量少 | +----------+-----------------+-----------------+------------------------------------------+-----------------+--------------------+-------------------+--------+--------+-------------------------------+ | 选择排序 | :math:`O(n^2)` | :math:`O(n^2)` | | :math:`O(n^2)` | | :math:`O(1)` | | 否 | 数据量少 | +----------+-----------------+-----------------+------------------------------------------+-----------------+--------------------+-------------------+--------+--------+-------------------------------+ | 插入排序 | :math:`O(n^2)` | :math:`O(n)` | 数据完全有序 | :math:`O(n^2)` | 数据逆序 | :math:`O(1)` | | 是 | 数组长度小于 47 | +----------+-----------------+-----------------+------------------------------------------+-----------------+--------------------+-------------------+--------+--------+-------------------------------+ | 归并排序 | :math:`n\log n` | | | :math:`n\log n` | | :math:`O(n)` | | 是 | | +----------+-----------------+-----------------+------------------------------------------+-----------------+--------------------+-------------------+--------+--------+-------------------------------+ | 快速排序 | :math:`n\log n` | :math:`n\log n` | 两个子问题规模都小于 :math:`\frac{n}{2}` | :math:`O(n^2)` | 一个子问题大小为零 | :math:`O(\log n)` | 是 | 否 | | +----------+-----------------+-----------------+------------------------------------------+-----------------+--------------------+-------------------+--------+--------+-------------------------------+ | 堆排序 | :math:`n\log n` | :math:`n\log n` | | :math:`n\log n` | | :math:`O(1)` | | 否 | | +----------+-----------------+-----------------+------------------------------------------+-----------------+--------------------+-------------------+--------+--------+-------------------------------+ | 希尔排序 | :math:`n^2` | :math:`O(n)` | 基本有序 | :math:`O(n^2)` | | :math:`O(1)` | | 否 | 中小型规模数据 | +----------+-----------------+-----------------+------------------------------------------+-----------------+--------------------+-------------------+--------+--------+-------------------------------+ | 计数排序 | :math:`n+k` | | | :math:`O(n^2)` | | :math:`k` | | 是 | 数据集中 :math:`n+k` | +----------+-----------------+-----------------+------------------------------------------+-----------------+--------------------+-------------------+--------+--------+-------------------------------+ | 桶排序 | :math:`n+k` | | | :math:`n+k` | | :math:`n+k` | | 不一定 | :math:`n+k` | +----------+-----------------+-----------------+------------------------------------------+-----------------+--------------------+-------------------+--------+--------+-------------------------------+ | 基数排序 | :math:`n+k` | | | :math:`n+k` | | :math:`n+k` | | 是 | 整数 10W-100W，以及非数字排序 | +----------+-----------------+-----------------+------------------------------------------+-----------------+--------------------+-------------------+--------+--------+-------------------------------+ 具有记忆功能的数据结构是栈 - 当数据有序时，冒泡排序、插入排序和希尔排序最快，是 :math:`O(n)` - 当数据量少时，归并排序快，快速排序慢 - 数据量大，有序性好时，快速排序最快 - 数据量大，有序性差时，堆排序最快 快速排序是内部排序中最好的方法，待排序的关键字是随机分布时，快速排序最快 对于不稳定的算法可以简单地记成：快选堆希（快速排序、选择排序、堆排序和希尔排序） 稳定的算法可以记为：插冒归基（插入排序、冒泡排序、归并排序、基数排序） 比较次数而言，平均情况下快排需要 nlog(n) 次，堆排序需要 n*2logn 插排，比较过的不再比较 归并排序， 分治，在治的时候 两个元素只比较一次，之后不再比较 选择排序，每次找最大值或者最小值，可能两个元素会多次比较 堆排序，堆删除第一个元素后，会有最后的元素和前面的元素的比较，可能存在某两个元素多次对比。 对于 topN 问题而言，使用选择排序最佳 [#topN]_ .. seealso:: - `[算法总结] 十大排序算法 `_ - `数据量极大时用什么排序方法比较好 `_ - `排序及其分类_张议的博客-CSDN博客_排序的种类 `_ .. [#topN] https://www.nowcoder.com/questionTerminal/e35afb8f29fd4ba5882f7654e77c1777 直接插入排序 **************************************** 插入排序的特征是第 :math:`n` 轮前 :math:`n` 个数字有序 插入排序的思想和方法及其简单，其思想简单概括如下：以 :math:`i` 为分界点，位于 :math:`i` 左侧的全部是有序的。每次将 :math:`i` 位置的元素取出，并移动左侧的元素，直至找到一个不小于 :math:`\text{array}[i]` 的元素，并将 :math:`\text{array}[i+1]` 插入到该元素的后面 其全部实现代码如下： .. code-block:: cpp void INSERT_SORT(int* array, size_t size) { for(size_t i = 2; i <= size; ++i) { int key = array[i]; int j = i - 1; while(j && array[j] < key) { array[j + 1] = array[j]; --j; } array[j + 1] = key; } } 折半插入排序 **************************************** 折半插入排序与直接插入排序类似，唯一不同的是在查找插入位置的时候使用了二分法查找插入位置。因此，插入排序只是减少了比较的次数，而没有更改元素移动的次数。 希尔排序 **************************************** 希尔排序因人名而得名，实际上是一种增量排序，是对直接插入排序的一种优化。希尔排序的方式可概括如下：取一个增量 :math:`k` ，每次将 :math:`i, i+k` 两个元素进行比较并交换。每次迭代将窗口大小减半，当窗口大小为一的迭代完成时，数组有序。 归并排序 **************************************** 归并排序的简单思想可以概述如下：假设我们有两堆分别有序且牌面朝下的牌，先将分别从左手牌和右手牌顶部抽出一张牌，并将其比较大小，如果左手牌比较大，就将左手牌放入中间牌，然后再抽出一张左手牌与已有的右手牌比较。依次重复上述内容，就将两副分别有序的牌组合成了一个有序的牌组。 在实际中我们可以将一个大的数组从中间分成两份，然后两份再分别进行细分，依次向下归下去，就得到若干个只有一个元素的数组，已知一个元素的数组肯定是有序的，如此两两合并，就将单元素的数组合成了一个有序的初始数组 在下面的实现中，假定所有元素不超过 *INT_MAX* ： .. code-block:: cpp int INT_MAX = std::numeric_limits::max(); void MERGE(int* array, size_t p, size_t q, size_t r) { int n1 = q - p + 1; int n2 = r - q; int* L = new int[n1 + 2]; int* R = new int[n2 + 2]; for(int i = 1; i <= n1; ++i) L[i] = array[i + p - 1]; for(int i = 1; i <= n2; ++i) R[i] = array[i + q]; L[n1 + 1] = INT_MAX; R[n2 + 1] = INT_MAX; size_t i = 1; size_t j = 1; for(size_t k = p; k <= r; ++k) { if(L[i] <= R[j]) { array[k] = L[i]; ++i; } else { array[k] = R[j]; ++j; } } delete[] L; delete[] R; } void MERGE_SORT(int* array, size_t p, size_t r) { if(p < r) { int q = (p + r) / 2; MERGE_SORT(array, p, q); MERGE_SORT(array, q + 1, r); MERGE(array, p, q, r); } } :math:`m` 个元素 :math:`k` 路归并的归并趟数 :math:`s=log_km` 冒泡排序 **************************************** 冒泡排序与堆排序略微相似，其在每次遍历数组的过程中，只比较相邻两个元素，并将较大元素交换到右侧。这样，一次遍历下来就会将最大元素交换到数组末尾。然后下次遍历的范围减一。当遍历范围为一时，整个数组有序。 .. code-block:: cpp void BUBBLESORT(int* array, size_t p, size_t r) { while(r != 1) { for(size_t lhs = p; lhs < r; ++lhs) if(array[lhs] > array[lhs + 1]) swap(array[lhs], array[lhs + 1]); --r; } } 快速排序 **************************************** 快速排序是一种实现起来非常简单的排序方式。快速排序最坏情况下的时间复杂度是 :math:`O(n^2)` ，但是其期望时间复杂度是 :math:`O(n\lg n)` 。这就导致快速排序实际上是排序中的最佳选择 快速排序在每一轮至少会导致基准位于正确的位置上 快速排序具有原址性 快速排序用到了与归并排序相同的分治算法，其思想可概括如下：将一个数组 *array* 划分为两部分，其中左侧的元素必定小于右侧的元素，然后再对这两部分继续划分，就这样，每个子数组的左侧都要小于右侧，当子数组的尺寸为二时，整个数组有序。分区算法是整个排序算法中的重中之重 在分区时，我们简单地将数组的最后一位 :math:`array[r]` 作为分组的分界点，划分完成后，左侧的元素都小于 :math:`array[r]` ，右侧的元素都大于 :math:`array[r]` .. code-block:: cpp size_t PARTITION(int* array, size_t p, size_t r); void QUICKSORT(int* array, size_t p, size_t r) { if(p < r) { size_t q = PARTITION(array, p, r); QUICKSORT(array, p, q - 1); QUICKSORT(array, q + 1, r); } } size_t PARTITION(int* array, size_t p, size_t r) { int x = array[r]; int i = p - 1; for(size_t j = p; j <= r - 1; ++j) { if(array[j] <= x) { ++i; swap(array[j], array[i]); } } swap(array[i + 1], array[r]); return i + 1; } 在上述分区过程中， :math:`i` 指向第一个不小于 :math:`array[r]` 的数， :math:`j` 指向第一个没被处理的数。这样，在 :math:`i` 和 :math:`j` 之间的数都是大于 :math:`array[r]` 的，没当出现一个不大于 :math:`array[r]` 的数，就将上述区间中第一个大于 :math:`array[r]` 的数交换到此位置 .. important:: - 在做题的时候分区是按照第一个元素为基准 - 每轮分区后，下一个分区节点是上一个基准的前一个元素 .. seealso:: - `三种快排及四种优化方式 `_ 直接选择排序 **************************************** 选择排序是一种思想很简单的排序方式，每次迭代从未排序的序列中选出一个最值并将其与未排序的序列的第一个元素交换 因为是使用了交换的方式，因此中间没有元素整体移动的过程 堆排序 **************************************** 堆排序是 *选择排序* 中的一种 *不稳定排序* 。具有 *原址性* ，时间复杂度为 :math:`O(n\log n)` 堆 ======================================== （二叉）堆是一种具有这样性质的一种数据结构： - 除了最底层外，其它各层都是满的（近似 **完全二叉树** ） - 父节点比子节点大/小 大顶堆是父节点比子节点大的堆，小顶堆则反之 借由二叉树知道的知识，我们可以得到大顶堆的性质： - 父节点 :math:`n` 的两个子节点分别为 :math:`2n` 和 :math:`2n+1` - 子节点 :math:`n` 的父节点为 :math:`\lfloor\frac{n}{2}\rfloor` - 堆的高度就是根节点到叶节点的最长简单路径上边的数目，对于一个含有 :math:`n` 个元素的堆而言，其高度为 :math:`\lfloor\lg n\rfloor` 堆中的元素在数组中是按照层序遍历的方式排布的 维护最大堆的性质 ======================================== 维护最大堆的性质比较简单。它的输出参数一共有三个：array、begin、end，分别代表了最大堆对应的数组和欲维护的最大堆的范围。在进行为维护时，我们假定节点的左子树和右子树都满足最大堆的定义，但是节点有可能小于其左孩子或右孩子。一旦节点与孩子节点发生了交换，那么孩子节点对应的子树就可能不满足最大堆的定义，这时只需要堆子树再进行一次最大堆的维护： .. code-block:: cpp void MAX_HEAPFIY(int *array, size_t begin, size_t end) { int l = LEFT(begin); int r = RIGHT(begin); size_t largest = begin; if(l <= end && array[l] > array[largest]) largest = l; if(r <= end && array[r] > array[largest]) largest = r; if(largest != begin) { swap(array[begin], array[largest]); MAX_HEAPFIY(array, largest, end); }; } **MAX_HEAPFIY** 的时间复杂度为 :math:`O(\lg n)` 建立堆 ======================================== 建立堆比较简单，只需要从堆的最后一个根节点向上依次调用 **MAX_HEAPFIY** 即可。根据二叉树的性质，我们可以知道最后一个根节点为 :math:`\lfloor\frac{n}{2}\rfloor` .. code-block:: cpp void BUILD_MAX_HEAP(int *array, size_t size) { for(size_t i = size / 2; i > 0; --i) MAX_HEAPFIY(array, i, size); } **BUILD_MAX_HEAP** 的时间复杂度为 :math:`O(n)` 堆排序算法 ======================================== 堆排序的算法更加简单，我们需要做的事情为：将给定的序列构建成最大堆 -> 将堆顶部的元素与堆末尾元素交换 -> 将堆尺寸减一 。该过程一直持续到堆的尺寸为二 .. code-block:: cpp void HEAPSORT(int *array, size_t size) { BUILD_MAX_HEAP(array, size); for(size_t heap_size = size; heap_size > 1; ) { swap(array[1], array[heap_size]); --heap_size; MAX_HEAPFIY(array, heap_size); } } **HEAPSORT** 的时间复杂度为 :math:`O(n\lg n)` ，因为调用了 :math:`n` 次 **BUILD_MAX_HEAP** 和 :math:`n-1` 次 **MAX_HEAPFIY** 完整代码 ======================================== 如此，一个完整的堆排序代码如下： .. code-block:: cpp #include using namespace std; #define LEFT(node) (node << 1) #define RIGHT(node) ((node << 1) + 1) #define PARENT(node) (node >> 1) void MAX_HEAPFIY(int *array, size_t begin, size_t end) { int l = LEFT(begin); int r = RIGHT(begin); size_t largest = begin; if(l <= end && array[l] > array[largest]) largest = l; if(r <= end && array[r] > array[largest]) largest = r; if(largest != begin) { swap(array[begin], array[largest]); MAX_HEAPFIY(array, largest, end); }; } void BUILD_MAX_HEAP(int *array, size_t size) { for(size_t i = size / 2; i >= 1; --i) MAX_HEAPFIY(array, i, size); } void HEAPSORT(int *array, size_t size) { BUILD_MAX_HEAP(array, size); for(size_t heap_size = size; heap_size >= 2;) { swap(array[1], array[heap_size]); --heap_size; MAX_HEAPFIY(array, 1, heap_size); } } int main() { int a[11] = { 0, 4, 12, 3, 5, 6, 1, 8, 100, 11, 23 }; HEAPSORT(a, 10); for(size_t i = 1; i < 11; ++i) { cout << a[i] << " "; } cout << endl; return 0; } 插入元素 ======================================== 插入元素是直接将元素插到最后，然后重新构建一次堆 删除元素 ======================================== 将需要删除的元素与最后的元素进行交换，然后重新构建堆 堆排序的 TopK 问题 ======================================== 利用堆结构解决 top K（这里是 min K）问题有两种实现方式，min K 为例： [#topk]_ 小顶堆思路：构建一个容量为 n 的堆，建堆时间为 n，此后每次都弹出堆顶元素（最小元素）再调整，一共弹 K 次，每次调整时间为 :math:`\log n` ，所以时间复杂度是 :math:`n+K\times\log n` ； 大顶堆思路：只维护一个容量为 K 的堆，所以建堆的复杂度为 K，此后遍历数组剩下的所有元素（n-K 个），每个元素都要和堆顶的元素进行比较，如果比堆顶大，则忽略（说明该元素不是最小 K 个值，概率比较难算，这里简单当作 :math:`\frac{n-K}{n}` ，复杂度是 1，如果比堆顶小（概率简单视作 :math:`\frac{K}{n}` ），则将堆顶替换为该元素并调整堆结构（称之为堆更新），每次更新（堆调整）的复杂度为 :math:`\log K` ，所以最坏时间代价为：:math:`K+(n-K)\times\log K` ； 结合概率平均每个元素要比较的次数为：:math:`\log K\times\frac{K}{n}+1\times\frac{n-K}{n}` ，所以总时间复杂度是： :math:`K+(n-K)\times(\frac{K\log K}{n}+1\times\frac{n-K}{n})` ； 下面我们来分析一下二者的代价，假设数据总量固定为 10w，要求 min K 问题，将 K 作为变量，画出二者的函数图像（如下），可见，对于不同的 K 值，方法二（大顶堆）普遍比方法一好（但是一定要注意把概率考虑进去，否则得出的结果是大顶堆的最坏情况）。 .. image:: assets/2021-08-28-03-07-57.png 而如果将 K 值固定为 1000，将数据总量 n 作为变量又如何呢？？同样的，画图观察（如下），可见，还是方法二好一点。 .. image:: assets/2021-08-28-03-09-08.png 局部堆（K 堆）方法的特点是，堆顶在比较过程中起到了关键作用，大部分情况下，数据都被堆顶元素给拒之门外，只有少部分数据能进入堆中更新数据，另外空间效率也比较优秀。 全局堆（N 堆）方法的特点是，当 K 非常小时，也能取得优秀的效率，但是当 K 增大时，代价就变大了，同时需要一个充分的空间来容纳所有数据。 结论：局部堆比全局堆好用，并且 :math:`\frac{K}{N}` 的值越大，差别越明显 .. [#topk] - `关于堆数据结构，下面描述中正确的有 `_ 总结： 也就是说，如果对于 minK 问题。两种选择： - 使用小顶堆：每次选择最小值，选择后对 n 个数据进行重排 - 使用大顶堆：只维护尺寸为 K 的堆，将剩余数据与堆顶比较。如果小于堆顶就将其插入堆，等到一趟遍历完成后堆顶是 minK 中最大的一个元素，整个堆就是所需要的元素。相比小顶堆的优势在于堆的尺寸只有 K。大大减小了堆的调整的代价 拓扑排序 **************************************** 拓扑排序：将有向图中所有顶点排成一个线性序列，使得图中任意一对顶点 :math:`u`和 :math:`v`，若边 :math:`∈E(G)` ，则 :math:`u` 在线性序列中出现在v之前。 #. 从有向图中没有入度的顶点开始 #. 依据顶点出度的指向进行对线性序列的逐渐加入 计数排序 **************************************** 计数排序是一种基于统计的排序，而不是基于比较的排序