浅谈排序

Nuyoah_awa · 2023-05-28 17:26:30 · 算法·理论

秩序就是正确的规律和事物永久的合理性。\textsf{———}菲尔丁

排序简介

定义

排序（Sorting algorithm）即将一组数据按某种顺序进行排列的算法。

排序算法多种多样，由于工作原理不同，性质也大多不同。

性质

稳定性

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

拥有稳定性这一特性的算法会让原本有相等键值的纪录维持相对次序，即如果一个排序算法是稳定的，当有两个相等键值的纪录 R 和 S，且在原本的列表中 R 出现在 S 之前，在排序过的列表中 R 也将会是在 S 之前。

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

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

时间复杂度

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

空间复杂度

与时间复杂度类似，空间复杂度用来描述算法空间消耗的规模。一般来说，空间复杂度越小，算法越好。

横向对比

在介绍各种排序前，我们先将他们做一个横向的对比。

选择排序

定义

选择排序（Selection sort）：

工作原理：\forall i \in [1, n] 每次找出第 i 小的元素（\min\limits_{j = i}^{j \le n}a_i），然后将这个元素与数组第 i 个位置上的元素交换。
稳定性：由于将第 i 小的元素和第 i 需要交换，这个算法是不稳定的。
时间复杂度：首先枚举第 i 小的数，然后枚举每个数找到第 i 小，时间复杂度是 \mathcal O(n ^ 2) 的。
例题：

P1177（排序模板，但是这道题 \mathcal O(n^2) 过不了）	P2240

P5740

code

void selection_sort(int* a, int n)
{
  for(int i = 1;i < n;i++)
  {
    int mn = i;
    for(int j = i + 1;j <= n;j++)
      if(a[j] < a[mn])
        mn = j;
    swap(a[i], a[mn]);
  }
  return ;
}

冒泡排序

定义

冒泡排序（Bubble sort）：

工作原理：与选择排序有相同之处，本质上都是使较小/大的数来到数列前面。冒泡排序没回检查相邻两数，如果前者较大，就将其交换。
稳定性：由于是相邻两数交换，且是前者较大才交换，所以是稳定的。
时间复杂度：每次扫一遍至少 1 个数就为，加上扫一遍的时间复杂度，总的时间复杂度是 \mathcal O(n ^ 2) 的。
例题：

P1177

code：

拓展

冒泡排序交换次数——即逆序对个数。

逆序对是 i < j 且 a_i > a_j 的有序数对 (i, j)。

使用冒泡排序求逆序对速度较慢，详解见下文-归并排序。

P1908

插入排序

定义

插入排序（Insertion sort）：

工作原理：创建一个“已排序”序列，将未排序的数依次插入这个序列中它该在的地方。
稳定性：
时间复杂度：
例题：

浅谈排序

秩序就是正确的规律和事物永久的合理性。\textsf{———}菲尔丁

排序简介

定义

性质

稳定性

时间复杂度

空间复杂度

横向对比

选择排序

定义

code

冒泡排序

定义

code：

拓展

插入排序

定义

计数排序

基数排序

快速排序

归并排序

堆排序

桶排序

希尔排序