排序算法

在生活中，排序无处不在，在购物搜索产品时，为了便于找到合适的产品，我们经常需要对搜索结果按价格高低排序，或按发货距离远近排序；在各种考试中，会根据成绩的高低来进行评判；游戏中，处处有分数排名，这些都是排序的一种应用体现。

按下来我们就通过对最简单的数字进行大小排序为例来讲解排序算法。

比如说，将下面一串数字，按从小到大进行排序。

6 5 1 2 8

经过排序，结果变成

1 2 5 6 8

如何调整顺序，最终将结果变得有序，有非常多的算法，我们主要介绍下面几种：

选择排序（Selection Sort）
冒泡排序（Bubble Sort）
插入排序（Insertion Sort）
快速排序（Quick Sort）
希尔排序（Shell Sort）
归并排序（Merge Sort）

排序算法是计算机科学中一个非常基础而重要的部分。不同的排序算法在时间复杂度、空间复杂度、稳定性和适用场景上各有特点，在学习这部分内容时注意对比分析。

排序代码基础模板

在讲解不同的排序算法时，我们使用了下面这样一个基础的代码模板。

#include <iostream>
using namespace std;

// 排序算法函数
void sort(int ary[], int n) {
  // 这里是具体的排序算法逻辑代码
}

const int MAX_LEN = 500;
int a[MAX_LEN];

int main() {
    int n;
    cin >> n;

  // 读入数据
    for (int i = 0; i < n; i++) cin >> a[i];

    // 调用排序算法函数
    sort(a, n);

    for (int i = 0; i < n; i++) cout << a[i] << " ";

    return 0;
}

我们要做的主要就是实现对应的排序算法函数 sort() 编写。

选择排序（Selection Sort）

基本思想

选择排序应该是所有排序中最简单的一种排序，其算法思想也非常好理解，每一轮找出数组中未排序部分的最小值（或最大值），然后将其与未排序部分的第一个元素交换位置（放到已排序部分的末尾）。

算法步骤

可以用下面四个步骤来描述选择排序的算法：

第 1 步，找出整个数组中最小的元素，与 a[0] 交换
第 2 步，找出 a[1] ~ a[n] 所有元素中的最小值，与 a[1] 交换
第 3 步，找出 a[2] ~ a[n] 所有元素中的最小值，与 a[2] 交换
依次下去，直接全部找完，完成排序

具体的排序过程用示意图表示如下：

实现代码

#include <iostream>
#include <cstdio>
using namespace std;


const int N = 100;
int a[N];


//排序算法的核心逻辑
// 每一轮将最小值拿出来，与 a[i] 交换
void selection_sort(int ary[], int n) {
  int min_index = 0;
  //排序算法的逻辑
  for (int i = 0; i < n - 1; i++) {
    min_index = i; // 用于记录每一轮最小值的下标
    for (int j = i + 1; j < n; j++) {
      if (ary[j] < ary[min_index]) min_index = j;
    }

    swap(ary[i], ary[min_index]);

    printf("第%d轮排序结果：", i + 1);
    for (int k = 0; k < n; k ++) cout << ary[k] << " ";
    cout << endl;
  }
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) cin >> a[i];

    // 排序算法
    selection_sort(a, n);

    // 排序后
    for (int i = 0; i < n; i++) cout << a[i] << " ";

    return 0;
}

输入数据：

5
6 5 1 2 8

输出结果：

第1轮排序结果：1 5 6 2 8
第2轮排序结果：1 2 6 5 8
第3轮排序结果：1 2 5 6 8
第4轮排序结果：1 2 5 6 8
1 2 5 6 8

注意，这里我们在排序算法函数 selection_sort() 中，添加了一段将每一轮排序的结果显示出来的辅助代码，这样更有助于我们对比理解算法的运行逻辑。为了节省代码篇幅，在后面的其它排序算法中，我们就只列出了排序函数的代码，也没有添加显示排序过程的辅助代码，大家有需要的话可以用类似的方法去添加，方便观察排序的过程。

代码优化

细心的同学可能已经发现，对于我们选择的数据来说，经过第 3 轮排序，结果已经完成排序了，第 4 轮实际上没有交换，也就是说第 3 轮后就不需要继续去比较排序了。

基于这样的判断，我们可以对上面的代码做出优化，一旦发现某一轮中没有任何交换产生，就直接进入下一轮。

下面是通过设定标志位来记录某一轮是否有交换产生，优化后的 selection_sort() 代码如下：

void selection_sort(int ary[], int n) {
  int min_index = 0;

  for (int i = 0; i < n - 1; i ++) {
    min_index = i;

    int swapped = 0; // 用于记录是否有交换产生的标志位
    for (int j = i + 1; j < n; j ++) {
      if (ary[j] < ary[min_index]) {
        swapped = 1;
        min_index = j;
      }
    }

    if (swapped == 0) continue;

    swap(ary[i], ary[min_index]);
  }
}

时间复杂度

• 最坏情况： $O(n^2)$ （无论数组是否有序，都需要遍历整个未排序部分） • 最优情况： $O(n^2)$ • 平均情况： $O(n^2)$

空间复杂度

• 空间复杂度： $O(1)$ ，仅使用常数级别的额外空间。

稳定性

• 不稳定：相同元素的相对位置可能会改变，因为最小元素的交换可能会移动相同元素的相对位置。

冒泡算法（Bubble Sort）

基本思想

冒泡算法，顾名思义，就是让越大的数不断往上冒，就像水底的泡泡往上冒一样。

冒泡排序的基本思想是通过重复遍历要排序的数列，比较每对相邻元素的大小，并在必要时交换它们的位置。每一轮遍历后，最大的元素都会被”冒泡”到它应该在的位置。

算法步骤

从数组的第一个元素开始，比较相邻的两个元素。
如果左边的元素大于右边的元素，就交换它们的位置。
对数组中未排序的部分重复上述步骤，直到最后一个元素。
经过一轮遍历后，最大的元素会被放到它最终的位置。
重复这个过程，每次减少需要排序的元素范围，直到整个数组都被排序。

实现代码

void bubble_sort(int ary[], int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (ary[j] > ary[j + 1]) {
        swap(ary[j], ary[j + 1]);
      }
    }
  }
}

冒泡排序过程展示

下面通过图示展示了冒泡算法的具体每一轮的排序过程。

第 1 轮

从第一个元素数字 6 开始，一直往上冒（其实是往右），第一轮结束时，6 直到 8 的前面（因为它比 8 小，被挡住，冒不上去了）。

i = 0 。i 记录的是轮数。
j 从 0 开始，直到 j < 4 。j 记录的是每一轮中的两两比较。

在这一轮中，共有 4 次比较，实际上只做了两次交换。

【TODO】下面图需要修改，第 3 次是需要交换的，而不是无交换。

第 2 轮

i = 1
j 从 0 开始，直到 j < 3

在这一轮中，共有 3 次比较，实际做了两次交换。

第 3 轮

i = 2
j 从 0 开始，直到 j < 2

在这一轮中，共有 2 次比较，实际上一次交换都没做。

第 4 轮

i = 3
j 从 0 开始，直到 j < 1

这一轮只有一次比较，也没有交换。

代码优化

同样的，细心的同学可能会发现，如果在某一轮的遍历中没有发生任何交换，说明该数组已经有序，也就没必要继续执行排序的操作了，这时就可以提前结束排序。

我们可以通过设置一个标志位来实现提前结束排序的功能。

优化的代码如下：

void bubble_sort(int ary[], int n) {
  for (int i = 0; i < n - 1; i++) {
    bool swapped = false;
    for (int j = 0; j < n - i - 1; j++) {
      if (ary[j] > ary[j + 1]) {
        swap(ary[j], ary[j + 1]);
        swapped = true;
      }
    }
    if (!swapped) break;
  }
}

时间复杂度

• 最坏情况： $O(n^2)$ （当数组是倒序时，需要进行大量交换） • 最优情况： $O(n)$ （当数组已经有序时，只需遍历一次） • 平均情况： $O(n^2)$

空间复杂度

• 空间复杂度：O(1)，仅使用常数级别的额外空间。

稳定性

• 稳定：相同元素的相对位置不会改变。

插入排序（Insertion Sort）

基本思想

插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法步骤

插入排序很像打牌时拿牌放牌的过程。

拿第 1 张牌，直接放在手中
拿第 2 张牌，我们需要看看这张牌与手中第 1 张牌哪个大，如果比手中的牌大，就放在第 1 张牌的右边；如果比手中的牌小，就放在第 1 张片的左边
拿第 3 张牌，先与手中最右边的牌比较哪个大，如果当前拿到的牌更大，则放在手中牌的最右边；如果拿到的牌更小，则依次从右至左去比较手中的牌，直到放下
依次下次，直接拿完牌

用拿牌来总结一下插入排序算法的核心思想，每一次从未排序的（桌面上的）牌中拿出一张，插入到已排序的（手中的）牌中，当拿完牌的时候，手上的牌就是一幅已经排好序的牌。

实现代码

void insert_sort(int ary[], int n) {
  for (int i = 1; i < n; i++) {
    for (int j = i; j >= 0 && ary[j] < ary[j -1]; j--) {
      swap(ary[j], ary[j - 1]);
    }
  }
}

排序过程展示

下面仍然通过图示来展示一下插入排序执行的整个过程：

第 1 轮

手上的牌是 6，刚拿起的牌是 5，比较一下，5 比 6 小，因此需要交换（也就是放到 6 的左边）。

这一轮执行前手上有一张牌，执行后手上两张牌，执行了一次比较。

第 2 轮

手上有两张牌，5 和 6，从桌面（数组中）拿起的牌是 1，依次比较，总共交换了两次。

执行后手上的牌有 3 张，依次是 1、5、6 。

第 3 轮

这时手上有 3 张牌，1、5、6，从桌面（数组中）拿起的牌是 2，依次比较，总共交换了 2 次。

执行后手上的牌有 4 张，依次是1、2、5、6 。

第 4 轮

这时手上有 4 张牌，1、2、5、6，从桌面（数组中）拿起的牌是 8，因为 8 比现有手上最右边的 6 还大，因此本轮直接跳过。

执行后手上的牌共有 5 张，依次是1、2、5、6、8 ，且完成最终排序。

时间复杂度

• 最坏情况：O(n^2)（当数组是倒序时） • 最优情况：O(n)（当数组已经有序时） • 平均情况：O(n^2)

空间复杂度

• 空间复杂度：O(1)，仅使用常数级别的额外空间。

稳定性

• 稳定：相同元素的相对位置不会改变。

快速排序（Quick Sort）

基本思想

快速排序是由 C.A.R. Hoare 在 1960 年提出的一种交换排序算法，它采用的是一种分治的策略（Divide → Conquer → Merge），将要排序的数据队列分割成较大和较小的两个子分区，然后递归地对这两个子分区进行同样的处理。

平时我们将快速排序简称为「快排」，之所以叫快排，一定有过人之处，平均来说，快排的效率都是比较高的，尤其是当待排序的数据量非常大的时候，像选择、冒泡或插入排序都可能无法很好地完成排序任务，快排的作用就显现出来了。因此快排也是竞赛中最常考的一种算法。

算法步骤

快速排序算法可以分为以下几个步骤：

确定分界点。 从数列中挑出一个元素，做为基准（Pivot），也就是分界点。
调整数列。 以基准作为分界点，将数列分成两个子数列，左边小，右边大，基准在中间位置，这个操作也被称为分区（Partition）操作。
递归处理左右两端子分区。 用同样的方式（上面三个步骤）对左右两端的两个子数列进行排序操作，直到不可分割为止。

确定分界点

确定分界点的方式有很多种，你可以自己决定采用哪种方式，下面是常见的几种方式：

选择第一个元素做为分界点
选择最后一个元素做为分界点
选择中间的元素作为分界点
随机选择一个元素作为分界点

本例中选择的是最后一个元素做为分界点。

关于调整数列

调整数列前面已经有提到，调整的内容就下面三部分

将小于分界点的元素放在分界点之前
将大于分界点的元素放在分界点之后
分界点在中间位置

调整的思想比较好理解，但最关键，也是最难的部分就是具体如何去调整。无论是在网络上搜索，还是查阅各种书籍资料，都有各式各样的调整方法。

这里介绍的方法是使用双指针的方法，调整时左右两边往中间收缩前进，实现得非常优雅，也比较好理解，也不占用额外的数组空间。

// 快速排序算法函数
void quick_sort(int ary[], int l, int r) {
  if (l >= r) return;

  int left = l; // 左侧开始的下标
  int right = r - 1; // 右侧开始的下标
  int pivot = ary[r]; // 设定最后一个元素为分界点

  while (left <= right) {

    while (left <= right && ary[left] < pivot) left ++;
    while (left <= right && pivot < ary[right]) right --;

    if (left <= right) {
      swap(ary[left], ary[right]);
      left++;
      right--;
    }
  }

  swap(ary[left], ary[r]);

  quick_sort(ary, l, left - 1);
  quick_sort(ary, left + 1, r);
}

快速排序过程展示

下面的图形展示了每一轮选择的分界点，以及根据调整算法分割而成的左右子数列。

从每个分支的叶子节点可以看到，经过多次分割并调整完后，最终排序完成。

接下来看看每次根据分界点分割并调整的过程。

第 1 次分割与调整

int left = l; // 左侧开始的下标
int right = r - 1; // 右侧开始的下标
int pivot = a[r]; // 设定最后一个元素为分界点

第 1 次分割整理，选择最后一个元素 a[n-1] 作为基准（Pivot），left 设置为 a[0] 的位置，right 设置为 a[n-1] 的位置，分割与整理的过程如下图所示。

左侧子序列分割调整

右侧子序列第 1 次分割调整

右侧子序列第 2 次分割调整

时间复杂度

• 最坏情况：O(n^2)（当基准选择不当，导致每次只分割一个元素时） • 最优情况：O(n log n)（当每次基准选择使得数组均匀分割时） • 平均情况：O(n log n)

空间复杂度

• 空间复杂度：O(log n)（在理想情况下，递归调用栈的深度为 log(n)）

稳定性

• 不稳定：由于交换操作可能改变相同元素的相对位置。

归并排序（Merge Sort）

基本思想

归并也是采用分治策略的一种排序算法。它的核心思想是将一个大的待排序序列分割成若干个子序列，然后对每个子序列进行递归排序，最后将排好序的子序列合并起来，得到一个完整的有序序列。

算法步骤

归并排序的基本步骤包括分割、合并、复制这三步。

分割： 将待排序序列从中间分割成两个子序列，分别对左右两个子序列进行递归排序，直到子序列中只剩下一个元素为止。
合并： 将两个有序子序列合并成一个有序序列，合并过程中需要比较左右两个子序列的元素大小，将较小的元素放入临时数组中，直到将两个子序列全部合并为止。
复制： 将临时数组中排好序的元素复制回原来的待排序序列中。

下面是归并排序的一个示意图，样例数据仍然是：

6 5 1 2 8

第 1 步：自上而下递归分割

第 2 步：自下而上合并

代码实现

void merge_sort(int ary[], int l, int r) {
  if (l >= r) return;

  int mid = (l + r) / 2;

  merge_sort(a, l, mid);
  merge_sort(a, mid + 1, r);

  int k = 0, i = l, j = mid + 1;

  while (i <= mid && j <= r) {
    if (ary[i] <= ary[j]) tmp[k++] = ary[i++];
    else tmp[k++] = ary[j++];
  }
  while (i <= mid) tmp[k++] = a[i++];
  while (j <= r) tmp[k++] = a[j++];

  for (int i = l, j = 0; i <= r; i++, j++) ary[i] = tmp[j];
}