跳转至

排序

排序算法多种多样,性质也大多不同。

稳定性

稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。

基数排序、计数排序(桶排序)、插入排序、冒泡排序、归并排序是稳定排序。

选择排序、堆排序、快速排序不是稳定排序。

时间复杂度

时间复杂度用来衡量一个算法的运行时间和输入规模的关系,类似的有空间复杂度,用来描述算法的空间消耗的规模。

简单计算复杂度的方法一般是统计“简单操作”的执行次数,有时候也可以直接数循环的层数来近似估计。

时间复杂度分为最坏时间复杂度、平均时间复杂度、最好时间复杂度等等。OI 竞赛中要考虑的一般是最坏时间复杂度,因为它代表的是算法运行水平的下界,在评测中不会出现更差的结果了。

基于比较的排序算法的时间复杂度下限是 O(n\log n)的。

当然也有不是 O(n\log n)的,桶排序的时间复杂度是 O(n),但是它是在「用空间换时间」,它的空间复杂度是 O(所排序的最大数 )

当待排序的关键码序列基本有序时,插入排序最快。

冒泡排序

冒泡排序是一种稳定的排序方法。

以升序为例,冒泡排序每次检查相邻两个元素,如果前面的元素大于后面的元素,就将相邻两个元素交换。当没有相邻的元素需要交换时,排序就完成了。

不难发现,我们最多需要扫描 n遍数组才能完成排序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void bubble_sort() {
  for (int i = 1; i <= n; i++) {
    bool flag = false;
    for (int j = 1; j < n; j++)
      if (a[j] > a[j + 1]) {
        flag = true;
        int t = a[j];
        a[j] = a[j + 1];
        a[j + 1] = t;
      }
    if (!flag) break;  //如果没有执行交换操作,说明数列已经有序
  }
}

在序列完全有序时,该算法只需遍历一遍数组,不用执行任何交换操作,时间复杂度为 O(n)。在最坏情况下,冒泡排序要执行 (n-1) \times n/2次交换操作,时间复杂度为 O(n^2)。在平均情况下,冒泡排序的时间复杂度也是 O(n^2)

插入排序

插入排序依次处理待排序的记录,每个记录和之前处理过的序列中的记录进行比较,然后插入到其中适当的位置。

时间复杂度是 O(n^2)

Shell 排序

Shell 排序是以它的发明者命名的,也称为缩小增量排序法。Shell 排序对不相邻的记录进行比较和移动:

  1. 将待排序序列分为若干子序列(每个子序列的元素在原始数组中间距相同)
  2. 对这些子序列进行插入排序
  3. 减小每个子序列中元素之间的间距,重复上述过程直至间距减少为 1

Shell 排序的复杂度和间距序列的选取(就是间距如何减小到 1)有关,比如“间距每次除以 3”的 Shell 排序的复杂度是 O(n^{3/2})

选择排序

每次找出第 i 小的记录,将这个记录与数组的第 i 个位置的记录交换。

时间复杂度为 O(n^2)

堆排序

对所有记录建

每次取出堆顶元素,就可以依次得到排好序的序列。

时间复杂度为 O(n\log n)

归并排序

归并排序是分治地来将一个数组排序。

归并排序分为三个过程:

  1. 将数列划分为两部分(直接分,而不是像快速排序那样要求保证相对大小关系)
  2. 递归到两个子序列中分别进行归并排序
  3. 合并两个子序列

不难发现,归并排序的核心是如何合并两个子序列,前两步都很好实现。

其实合并的时候也不难操作。注意到两个子序列在第二步中已经保证了都是有序的了,第三步中实际上是想要把两个有序数列合并起来。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void merge(int ll, int rr) {
  // 用来把 a[ll.. rr - 1] 这一区间的数排序。 t 数组是临时存放有序的版本用的。
  if (rr - ll <= 1) return;
  int md = ll + (rr - ll >> 1);
  merge(ll, md);
  merge(md, rr);
  int p = ll, q = md, s = ll;
  while (s < rr) {
    if (p >= md || (q < rr && a[p] > a[q])) {
      t[s++] = a[q++];
      // ans += md - p;
    } else
      t[s++] = a[p++];
  }
  for (int i = ll; i < rr; ++i) a[i] = t[i];
}

由于 || 是短路运算符,这里面 if 判断的情况是“第一部分已经完全合并完了”或者“两个都没有合并完,且前一个的队首要大于后一个”,这两种情况都是要把后一个子序列的队首放到新序列的当前位置中。

逆序对

归并排序还可以用来求逆序对的个数。

所谓逆序对,就是数对 (i, j),满足 a[i] > a[j]i < j

可以用树状数组线段树等数据结构来求,也可以用归并排序来求。

具体来说,上面归并排序中间注释掉的 ans += md - p 就是在统计逆序对个数。

是因为,那里把靠后的数放到前面了(较小的数放在前面),所以这个数的原来位置以前的、比它大的数都会和他形成逆序对,而这个个数就是还没有合并进去的数的个数,即为 md - p

使用归并排序求逆序对的时间复杂度也是 O(n \log n)

参考

https://www.geeksforgeeks.org/merge-sort/

快速排序

快速排序是分治地来将一个数组排序。

快速排序分为三个过程:

  1. 将数列划分为两部分(不是直接分,要求保证相对大小关系)
  2. 递归到两个子序列中分别进行快速排序
  3. 不用合并,因为此时数列已经完全有序

和归并排序不同,第一步并不是直接分成前后两个序列,而是在分的过程中要保证相对大小关系。

第三步中的序列已经分别有序且第一个序列中的数都小于第二个数,所以直接拼接起来就好了。

具体来说,第一步要是要把数列分成两个部分,然后保证前一个子数列中的数都小于后一个子数列中的数。

怎么操作呢?为了保证平均时间复杂度,一般是随机选择一个数 m 来当做两个子数列的分界。

之后,维护一前一后两个指针 p 和 q,依次考虑当前的数是否放在了应该在的位置(前还是后),当前位置放对了之后,再移动指针继续处理,直到两个指针相遇。

如果当前的数没放对呢?比如说如果后面的指针 q 遇到了一个比 m 小的数,那么可以交换 p 和 q 位置上的数,再把 p 向后移一位。

其实,快速排序没有指定应如何具体实现第一步,不论是选择 m 的过程还是划分的过程,都不是只有一种实现方法。

注意,一般我们说的快速排序的时间复杂度是平均为 O(N\log N),最坏是 O(n^2),只不过实践中几乎不可能达到最坏情况。

其实,在选择 m 的过程中使用Median of Medians算法,就可以保证最坏时间复杂度为 O(N\log N),但是由于 j 小微复杂,实践中一般不使用。

STL

C 函数模板库实现了快速排序,即 stdlib.h 当中的 qsort

但在 OI 相关比赛当中,更为常见的库排序函数是 C++ algorithm 库中的 std::sort 函数。

C++ 标准并未严格要求此函数的实现算法,具体实现取决于编译器。

旧版 C++ 标准中仅要求它的平均时间复杂度是 O(N\log N)的,但在 C++11 中要求它的最坏时间复杂度是 O(N\log N)的。可以查阅std::sort()

libstdc++libc++中使用的都是Introsort

Introsort 限制了快速排序的分治深度,当分治达到一定深度之后,改用最坏时间复杂度为 O(N\log N)的排序算法(比如堆排序)来给子数组排序。

Introsort 的这个限制使得它的最坏时间复杂度是 O(N\log N)的。

快速用法:

1
2
3
// a[0] .. a[n - 1] 是放了元素的
std::sort(a, a + n);
// 这句代码直接修改 a 数组里的元素顺序,使得现在它是从小到大排列的

线性找第 k 大的数

找第 k 大的数,最简单的方法是先排序,然后直接找到第 k 大的位置的元素。这样做的时间复杂度是 O(N\log N),对于这个问题来说很不划算。事实上,我们有 O(n)的解法。

考虑快速排序的划分过程,在快速排序的“划分”结束后,数列 A[p \cdots r]]被分成了 A[p \cdots q]A[q+1 \cdots r],此时可以按照左边元素的个数( q - p + 1)和 k 的大小关系来判断是只在左边还是只在右边递归地求解。

可以证明,在期望意义下,程序的时间复杂度为 O(n)

参考

https://stackoverflow.com/questions/22339240/what-algorithms-are-used-in-c11-stdsort-in-different-stl-implementations

https://en.cppreference.com/w/cpp/algorithm/sort

计数排序

计数排序也称桶排序,可以在 O(n)的时间内排序,但是它要求所有的数都出现在一定的范围内。

注意区分基数排序

算法流程顾名思义,就是记录每一个数出现了多少次,然后从小到大依次输出。

一般考虑的是某一范围内的整数,但是计数排序也可以和离散化一起使用,来对浮点数、大整数进行计数排序。

基数排序

基數排序是将待排序码拆分成多个部分分别来比较。

按照排序码的先后顺序,分为两种:

  1. 高位优先(MSD) 先对高位排序,分成若干子序列,对每个子序列根据较低位排序……是一个分、分、……、分、收的过程。
  2. 低位优先(LSD) 从低位开始,对于排好的序列用次低位排序……(每次排序的都是全体元素)是一个分、收、分、收……分、收的过程

低位优先速度较快,便于处理,更常用。

基数排序对关键码值进行 O(\log_r n)次运算,因此处理 n 个不同的关键码时,基数排序的时间代价为 O(n \log n)

参考

http://atool.org/sort.phpATool 的排序演示动画
https://www.geeksforgeeks.org/counting-sort/

排序的应用

借助排序,我们可以降低求解问题所需要的时间复杂度。

考虑一个数列,你需要检查其中是否有元素相等。

一个朴素的做法是检查每一个数对,并判断这一对数是否相等。时间复杂度是 O(n^2)

我们不妨先对这一列数排序,之后不难发现:如果有相等的两个数,它们一定在新数列中处于相邻的位置上。这时,只需要 O(n)地扫一遍新数列了。总的时间复杂度是排序的复杂度( O(n\log n))。

排序也是二分查找所要做的预处理工作。在排序后使用二分查找,我们可以在 O(\log n)的时间内在序列中查找指定的元素。


评论