常见排序算法

排序算法的评价维度

　　运行效率 ：我们期望排序算法的时间复杂度尽量低，且总体操作数量较少（时间复杂度中的常数项变小）。对于大数据量的情况，运行效率显得尤为重要。

　　就地性：顾名思义，原地排序通过在原数组上直接操作实现排序，无须借助额外的辅助数组，从而节省内存。通常情况下，原地排序的数据搬运操作较少，运行速度也更快。

　　稳定性：稳定排序在完成排序后，相等元素在数组中的相对顺序不发生改变。

　　稳定排序是多级排序场景的必要条件。假设我们有一个存储学生信息的表格，第 1 列和第 2 列分别是姓名和年龄。在这种情况下，非稳定排序可能导致输入数据的有序性丧失：

1
# 输入数据是按照姓名排序好的
2
# (name, age)
3
  ('A', 19)
4
  ('B', 18)
5
  ('C', 21)
6
  ('D', 19)
7
  ('E', 23)
8

9
# 假设使用非稳定排序算法按年龄排序列表，
10
# 结果中 ('D', 19) 和 ('A', 19) 的相对位置改变，
11
# 输入数据按姓名排序的性质丢失
12
  ('B', 18)
13
  ('D', 19)
14
  ('A', 19)
15
  ('C', 21)
1 collapsed line
16
  ('E', 23)

　　自适应性：自适应排序能够利用输入数据已有的顺序信息来减少计算量，达到更优的时间效率。自适应排序算法的最佳时间复杂度通常优于平均时间复杂度。

　　是否基于比较：基于比较的排序依赖比较运算符（<、=、>）来判断元素的相对顺序，从而排序整个数组，理论最优时间复杂度为 O(nlog⁡n) 。而非比较排序不使用比较运算符，时间复杂度可达 O(n) ，但其通用性相对较差。

　　‍

　　复杂度为$O(n^2)$的简单排序方式，为：冒泡、选择、插入

　　线性对数阶 $O(nlog_2n)$ 排序：快速排序、堆排序和归并排序

　　‍

选择排序

　　选择排序（selection sort）：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。

1
/* 选择排序 */
2
void selectionSort(vector<int> &nums) {
3
    int n = nums.size();
4
    // 外循环：[i, n-1)，n-1不需要遍历，一定是最大
5
    // 最后一个元素不需要遍历，因为最后一个元素一定是最大的。
6
    for (int i = 0; i < n - 1; i++) {
7
        // 内循环：找到未排序区间内的最小元素，k只是作为记录。实际遍历的还是[i,n]未排序区间
8
        int k = i;
9
        for (int j = i + 1; j < n; j++) {
10
            if (nums[j] < nums[k])
11
                k = j; // 记录最小元素的索引
12
        }
13
        // 将该最小元素与未排序区间的首个元素交换
14
        swap(nums[i], nums[k]);
15
    }
1 collapsed line
16
}

算法特性

时间复杂度为 **$O(n^2)$** 、非自适应排序：外循环共 n−1 轮，第一轮的未排序区间长度为 n ，最后一轮的未排序区间长度为 2 ，即各轮外循环分别包含 n、n−1、…、3、2 轮内循环，求和为 $(n−1)(n+2)/2$。
空间复杂度为 **$O(1)$** 、原地排序：指针 i 和 j 使用常数大小的额外空间。
非稳定排序：在交换元素时，因此可能出现元素相同时被交换到不同的位置，如图

　　‍

冒泡排序

　　「冒泡排序 bubble sort」通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样,
因此得名冒泡排序。实际上，冒泡排序和选择排序原理类似，但冒泡排序的效率更低，因为每一次都需要交换，而选择排序只有在确定是最小/最大的时候才会交换。

1
/* 冒泡排序 */
2
void bubbleSort(vector<int> &nums) {
3
    // 外循环：未排序区间为 [0, i]
4
    for (int i = nums.size() - 1; i > 0; i--) {
5
        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
6
        for (int j = 0; j < i; j++) {
7
            if (nums[j] > nums[j + 1]) {
8
                // 交换 nums[j] 与 nums[j + 1]
9
                // 这里使用了 std::swap() 函数
10
                swap(nums[j], nums[j + 1]);
11
            }
12
        }
13
    }
14
}

算法特性

时间复杂度为 **$O(n^2)$** 、非自适应排序：外循环共 n−1 轮，第一轮的未排序区间长度为 n-1 ，最后一轮的未排序区间长度为 1 ，即各轮外循环分别包含 n−1、…、3、2 、1轮内循环，求和为 $(n−1)n/2$。而如果引入优化一，则最佳情况下，时间复杂度可达到 O(n) ，即数据全部有序的情况下，只遍历一次就可以得出结果。
空间复杂度为 **$O(1)$** 、原地排序：指针 i 和 j 使用常数大小的额外空间。
稳定排序：在交换元素时，遇到相同的元素不会交换。

‍

效率优化

优化一：设置标志位

　　我们发现，如果某轮“冒泡”中没有执行任何交换操作，说明数组已经完成排序，可直接返回结果。因此，可以增加一个标志位 flag 来监测这种情况，一旦出现就立即返回。

　　经过优化，冒泡排序的最差时间复杂度和平均时间复杂度仍为 $O(n^2)$ ；但当输入数组完全有序时，可达到最佳时间复杂度 $O(n)$。

1
/* 冒泡排序（标志优化）*/
2
void bubbleSortWithFlag(vector<int> &nums) {
3
    // 外循环：未排序区间为 [0, i]
4
    for (int i = nums.size() - 1; i > 0; i--) {
5
        bool flag = false; // 初始化标志位
6
        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
7
        for (int j = 0; j < i; j++) {
8
            if (nums[j] > nums[j + 1]) {
9
                // 交换 nums[j] 与 nums[j + 1]
10
                // 这里使用了 std::swap() 函数
11
                swap(nums[j], nums[j + 1]);
12
                flag = true; // 记录交换元素
13
            }
14
        }
15
        if (!flag)
3 collapsed lines
16
            break; // 此轮“冒泡”未交换任何元素，直接跳出
17
    }
18
}

优化二：设置结束边界

　　参考：冒泡排序及其优化（三种优化）

　　除了检测是否有交换外，还可以记录上一次交换的位置。最后一次交换的位置之后的数据都是有序的，可以记录上一次最后交换的位置，作为下一次循环的结束边界。

1
/* 冒泡排序（边界）*/
2
void bubbleSortWithFlag(vector<int> &nums) {
3
    int lastSwap = nums.size() - 1;
4
    // 外循环：未排序区间为 [0, i]
5
    for (int i = nums.size() - 1; i > 0; i--) {
6
        int thisTurnLastSwap = lastSwap;
7
        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
8
        for (int j = 0; j < thisTurnLastSwap; j++) {
9
            if (nums[j] > nums[j + 1]) {
10
                // 交换 nums[j] 与 nums[j + 1]
11
                // 这里使用了 std::swap() 函数
12
                swap(nums[j], nums[j + 1]);
13
                lastSwap = j;
14
            }
15
        }
4 collapsed lines
16
        if (thisTurnLastSwap == lastSwap)
17
            break; // 此轮“冒泡”未交换任何元素，直接跳出
18
    }
19
}

　　这里将优化一的思想融入了。

优化三：双向冒泡排序

　　参考：最简单的冒泡排序还能怎么优化?

　　双向冒泡排序，又叫鸡尾酒排序（Cocktail Sort）。

　　它的过程是：先从左往右比较一次，再从右往左比较一次，然后又从左往右比较一次，以此类推。

　　适用于大部分数据已经排序好的情况，可以减少已排序好数据的比较轮数。

1
/* 冒泡排序（双向冒泡）*/
2
function bubbleSortOpt3(vector<int> &nums){
3
    // <== 设置每一轮循环的开始与结束位置
4
    int start = 0, end = nums.size() - 1;
5

6
    while(start < end){
7
        for(int i = start; i < end; i++){ // 从start位置end位置过一遍安排最大值的位置
8
            if(nums[i] > nums[i+1]){
9
                swap(nums[i], nums[i+1]);
10
            }
11
        }
12
        end--; // <== 由于当前最大的数已经放到了 end 位置, 故 end 位置向前移动
13

14
        for(int i = end; i > start; i--){ // 从end向start位置过一遍, 安排最小值的位置
15
            if(nums[i] < nums[i-1]){
6 collapsed lines
16
                swap(nums[i], nums[i-1]);
17
            }
18
        }
19
        start++; // <== 由于当前最小的数已经放到了 start 位置, 故 start 位置向后移动
20
    }
21
}

插入排序

　　插入排序（insertion sort）是一种简单的排序算法，它的工作原理与手动整理一副牌的过程非常相似。

　　具体来说，我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。

　　设基准元素为 base ，我们需要将从目标索引到 base 之间的所有元素向右移动一位，然后将 base 赋值给目标索引。

　　插入排序的整体流程如图 11-7 所示。

初始状态下，数组的第 1 个元素已完成排序。
选取数组的第 2 个元素作为 base ，将其插入到正确位置后，数组的前 2 个元素已排序。
选取第 3 个元素作为 base ，将其插入到正确位置后，数组的前 3 个元素已排序。

以此类推，在最后一轮中，选取最后一个元素作为 base ，将其插入到正确位置后，所有元素均已排序。

1
/* 插入排序 */
2
void insertionSort(vector<int> &nums) {
3
    // 外循环：已排序区间为 [0, i-1]
4
    for (int i = 1; i < nums.size(); i++) {
5
        int base = nums[i], j = i - 1;
6
        // 内循环：将 base 插入到已排序区间 [0, i-1] 中的正确位置
7
        while (j >= 0 && nums[j] > base) {
8
            nums[j + 1] = nums[j]; // 将 nums[j] 向右移动一位
9
            j--;
10
        }
11
        nums[j + 1] = base; // 将 base 赋值到正确位置
12
    }
13
}

算法特性

时间复杂度为 **$O(n^2)$** 、自适应排序：在最差情况下，每次插入操作分别需要循环 n−1、n−2、…、2、1 次，求和得到 (n−1)n/2 ，因此时间复杂度为 $O(n^2)$ 。在遇到有序数据时，插入操作会提前终止。当输入数组完全有序时，插入排序达到最佳时间复杂度 $O(n)$ 。
空间复杂度为 **$O(1)$** 、原地排序：指针 i 和 j 使用常数大小的额外空间。
稳定排序：在插入操作过程中，我们会将元素插入到相等元素的右侧，不会改变它们的顺序。

插入排序的优势

　　插入排序的时间复杂度为 $O(n^2)$ ，而我们即将学习的快速排序的时间复杂度为 $O(n\ log\ ⁡n)$ 。尽管插入排序的时间复杂度更高，但在数据量较小的情况下，插入排序通常更快。

　　这个结论与线性查找和二分查找的适用情况的结论类似。快速排序这类 $O(n\ log⁡\ n)$ 的算法属于基于分治策略的排序算法，往往包含更多单元计算操作。而在数据量较小时，$n^2$ 和 $n\ log\ ⁡n$ 的数值比较接近，复杂度不占主导地位，每轮中的单元操作数量起到决定性作用。

　　实际上，许多编程语言（例如 Java）的内置排序函数采用了插入排序，大致思路为：对于长数组，采用基于分治策略的排序算法，例如快速排序；对于短数组，直接使用插入排序。

　　虽然冒泡排序、选择排序和插入排序的时间复杂度都为 $O(n^2)$ ，但在实际情况中，插入排序的使用频率显著高于冒泡排序和选择排序，主要有以下原因。

冒泡排序基于元素交换实现，需要借助一个临时变量，共涉及 3 个单元操作；插入排序基于元素赋值实现，仅需 1 个单元操作。因此，冒泡排序的计算开销通常比插入排序更高。
选择排序在任何情况下的时间复杂度都为 $O(n^2)$ 。如果给定一组部分有序的数据，插入排序通常比选择排序效率更高。
选择排序不稳定，无法应用于多级排序。

快速排序

　　快速排序（quick sort）是一种基于分治策略的排序算法，运行高效，应用广泛。和归并排序相同点都是使用分治策略，不同点在与快速排序是根据基准数划分，先划分，再排序，归并排序是先分组，再排序，再合并。

　　快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。具体来说，哨兵划分的流程如图 11-8 所示。

选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端。
设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素。
循环执行步骤 2. ，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线。
对左右两个子数组继续快速排序。

1
/* 哨兵划分 */
2
int partition(vector<int> &nums, int left, int right) {
3
    // 以 nums[left] 为基准数
4
    int i = left, j = right;
5
    while (i < j) {
6
        while (i < j && nums[j] >= nums[left])
7
            j--;                // 从右向左找首个小于基准数的元素
8
        while (i < j && nums[i] <= nums[left])
9
            i++;                // 从左向右找首个大于基准数的元素
10
        swap(nums[i], nums[j]); // 交换这两个元素
11
    }
12
    swap(nums[i], nums[left]);  // 将基准数交换至两子数组的分界线
13
    return i;                   // 返回基准数的索引
14
}
15

11 collapsed lines
16
/* 快速排序 */
17
void quickSort(vector<int> &nums, int left, int right) {
18
    // 子数组长度为 1 时终止递归
19
    if (left >= right)
20
        return;
21
    // 哨兵划分
22
    int pivot = partition(nums, left, right);
23
    // 递归左子数组、右子数组
24
    quickSort(nums, left, pivot - 1);
25
    quickSort(nums, pivot + 1, right);
26
}

算法特性

时间复杂度为 **$O(n\ log\ n)$** 、非自适应排序：在平均情况下，哨兵划分的递归层数为 log⁡n ，每层中的总循环数为 n ，总体使用 $O(n\ log⁡\ n)$时间。在最差情况下，每轮哨兵划分操作都将长度为 n 的数组划分为长度为 0 和 n−1 的两个子数组，此时递归层数达到 n ，每层中的循环数为 n ，总体使用 $O(n^2)$时间。
空间复杂度为 **$O(1)$** 、原地排序：指针 i 和 j 使用常数大小的额外空间。
非稳定排序：在交换基准元素时，有可能会使基准元素被交换到相等元素的后边。

效率优化

优化一：基准数优化

　　快速排序在某些输入下的时间效率可能降低。举一个极端例子，假设输入数组是完全倒序的，由于我们选择最左端元素作为基准数，那么在哨兵划分完成后，基准数被交换至数组最右端，导致左子数组长度为 n−1、右子数组长度为 0 。如此递归下去，每轮哨兵划分后都有一个子数组的长度为 0 ，分治策略失效，快速排序退化为“冒泡排序”的近似形式。

　　为了尽量避免这种情况发生，我们可以优化哨兵划分中的基准数的选取策略。例如，我们可以随机选取一个元素作为基准数。然而，如果运气不佳，每次都选到不理想的基准数，效率仍然不尽如人意。

　　需要注意的是，编程语言通常生成的是“伪随机数”。如果我们针对伪随机数序列构建一个特定的测试样例，那么快速排序的效率仍然可能劣化。

　　为了进一步改进，我们可以在数组中选取三个候选元素（通常为数组的首、尾、中点元素），并将这三个候选元素的中位数作为基准数。这样一来，基准数“既不太小也不太大”的概率将大幅提升。当然，我们还可以选取更多候选元素，以进一步提高算法的稳健性。采用这种方法后，时间复杂度劣化至$O(n^2)$的概率大大降低。

1
int medianThree(vector<int> &nums, int left, int mid, int right) {
2
        int l = nums[left], r = nums[right], m = nums[mid];
3
        if((l <= m && m <= r) || (r <= m && m <= l)) {
4
            return mid;
5
        }
6
        if((m <= l && l <= r) || (r <= l && l <= m)) {
7
            return left;
8
        }
9
        return right;
10
    }
11

12
    int partition(vector<int> &nums, int left, int right) {
13
        int i = left, j = right;
14
        int mid = left + (right - left) / 2;
15
        mid = medianThree(nums, left, mid, right);
14 collapsed lines
16
        swap(nums[left], nums[mid]);
17
        while (i < j) {
18
            while (i < j && nums[j] >= nums[left]) {
19
                j--;
20
            }
21

22
            while (i < j && nums[i] <= nums[left]) {
23
                i++;
24
            }
25
            swap(nums[i], nums[j]);
26
        }
27
        swap(nums[left], nums[i]);
28
        return i;
29
    }

　　c++的库函数std::sort函数（基于快速排序、堆排序和插入排序的混合算法）中快排部分，也采用了基准数优化。

1
  template<typename _Iterator, typename _Compare>
2
    _GLIBCXX20_CONSTEXPR
3
    void
4
    __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
5
         _Iterator __c, _Compare __comp)
6
    {
7
      if (__comp(__a, __b))
8
  {
9
    if (__comp(__b, __c))
10
      std::iter_swap(__result, __b);
11
    else if (__comp(__a, __c))
12
      std::iter_swap(__result, __c);
13
    else
14
      std::iter_swap(__result, __a);
15
  }
19 collapsed lines
16
      else if (__comp(__a, __c))
17
  std::iter_swap(__result, __a);
18
      else if (__comp(__b, __c))
19
  std::iter_swap(__result, __c);
20
      else
21
  std::iter_swap(__result, __b);
22
    }
23

24
  template<typename _RandomAccessIterator, typename _Compare>
25
    _GLIBCXX20_CONSTEXPR
26
    inline _RandomAccessIterator
27
    __unguarded_partition_pivot(_RandomAccessIterator __first,
28
        _RandomAccessIterator __last, _Compare __comp)
29
    {
30
      _RandomAccessIterator __mid = __first + (__last - __first) / 2;
31
      std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
32
          __comp);
33
      return std::__unguarded_partition(__first + 1, __last, __first, __comp);
34
    }

优化二：尾递归优化-空间优化

　　在某些输入下，快速排序可能占用空间较多。以完全有序的输入数组为例，设递归中的子数组长度为 m ，每轮哨兵划分操作都将产生长度为 0 的左子数组和长度为 m−1 的右子数组，这意味着每一层递归调用减少的问题规模非常小（只减少一个元素），递归树的高度会达到 n−1 ，此时需要占用 O(n) 大小的栈帧空间。

　　为了防止栈帧空间的累积，我们可以在每轮哨兵排序完成后，比较两个子数组的长度，仅对较短的子数组进行递归。由于较短子数组的长度不会超过 n/2 ，因此这种方法能确保递归深度不超过 $log⁡\ n$，从而将最差空间复杂度优化至 $O(log\ ⁡n)$ 。代码如下所示：

1
/* 快速排序（尾递归优化） */
2
void quickSort(vector<int> &nums, int left, int right) {
3
    // 子数组长度为 1 时终止
4
    while (left < right) {
5
        // 哨兵划分操作
6
        int pivot = partition(nums, left, right);
7
        // 对两个子数组中较短的那个执行快速排序
8
        if (pivot - left < right - pivot) {
9
            quickSort(nums, left, pivot - 1); // 递归排序左子数组
10
            left = pivot + 1;                 // 剩余未排序区间为 [pivot + 1, right]
11
        } else {
12
            quickSort(nums, pivot + 1, right); // 递归排序右子数组
13
            right = pivot - 1;                 // 剩余未排序区间为 [left, pivot - 1]
14
        }
15
    }
1 collapsed line
16
}

注意

　　在快速排序的分区算法中，while 循环的顺序 与 基准元素的位置 密切相关，不能随意颠倒。原因主要有以下两个关键点，并且根据基准位置的不同，处理方式也不同：

1. 确保每个元素都能正确与基准比较：

　　因为程序是顺序执行的，在 i 和 j 相差1时，先执行的 while循环，会多一次比较机会，这决定了最后一次比较中的两个数据能够被正确的划分。

右侧基准时：i 指针从左向右寻找第一个 大于基准的元素，j 指针从右向左寻找 小于基准的元素。如果 i 指针先行，它能确保左侧所有元素与基准进行比较，确保小于基准的元素正确地放置在左区间。
- 如果颠倒顺序让 j 指针先行，可能导致某些靠近基准的元素（特别是小于基准的）无法与基准比较，破坏分区的完整性。
左侧基准时：则相反，应该让 j 指针先行，这样可以确保右侧的元素都能正确地与基准比较，找到第一个小于基准的元素。

2. 确保最后交换时基准与大于等于基准的元素交换：

右侧基准时：如果 i 指针先行，最后一次交换时，i 会停在 大于等于基准的元素 上，这样交换后能确保分区结构正确，即 左区间 < 基准 < 右区间。
- 如果 j 指针先行，则可能导致 i 停在一个 小于等于基准的元素 上，导致错误分区，破坏了左小右大的结构。
左侧基准时：同理，应让 j 指针先行，这样确保最后交换时基准能够与 小于等于基准的元素 交换，保证 左区间 < 基准 < 右区间。

实例说明

　　例如当 i = 0, j = 1，且 nums[0] <= nums[right] 时，上面的代码，会先执行 i++的循环，则 nums[i]就能够和基准 nums[right] 比较，i = j = 1。而若 j— 的循环在最前面，则先执行 j—的循环，这之后 i < j就不成立了，nums[i]就无法和基准比较，那么 i = j =0，此时大循环结束，需要交换nums[right] 和 nums[i]（i=0），而 nums[0] <= nums[right]，如果交换，则出现了 基准 < 右区间 > 左区间 的错误分区。正确的交换应该是 nums[right] 和 nums[1]，保证 左区间 < 基准 < 右区间。

　　下面给出上述阐述的数组：

1
原数组：
2
id   0 1 2 3
3
nums 1 5 3 2
4

5
right = 3, i = 1, j = 1, swap(nums[right], nums[i])后：
6
id   0 1 2 3
7
nums 1 2 3 5
8

9
right = 3, i = 0, j = 0, swap(nums[right], nums[i])后：
10
id   0 1 2 3
11
nums 2 5 3 1

　　所以如果我们把基准指针从 left 替换为 right，相应地，while循环的顺序就需要改变为：

1
while (i < j) {
2
    while (i < j && nums[i] <= nums[right]) {// 从左侧开始找第一个大于基准的位置
3
        i++;
4
    }
5
    while (i < j && nums[j] >= nums[right]) {// 从右侧开始找第一个小于基准的位置
6
        j--;
7
    }
8
    swap(nums[i], nums[j]);
9
}
10
swap(nums[right], nums[i]);

插曲

　　在 C++ 标准库中，std::sort 函数是一种用于对容器或数组中的元素进行排序的函数。它是基于快速排序（Quicksort）、堆排序（Heapsort）和插入排序（Insertion Sort）的混合算法，称为 Introsort。

关键算法步骤

Introsort 是基于快速排序的，但会在递归深度达到一定程度时切换到堆排序，以防止最坏情况下快速排序退化为 $O(n^2)$ 的时间复杂度。
在排序过程中，对小规模区间使用插入排序，以利用其在小数据集上的高效性。

　　leetcode上的排序题目：912. 排序数组中的测试数据增加了有序大数组，对快速排序不友好，会退化为类似冒泡排序的 $O(n^2)$算法，因此，使用快排需要经过基准数优化才能通过，另外，堆排序在这个题目中表现很好，因此C++中的sort函数也会快很多。

归并排序

　　待续。

堆排序

　　待续。