排序稳定性

定义：假定在待排序的序列中，存在多个相同值，若经过排序，这些值的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

排序稳定性很容易被认为是排序速度的稳定性，比如插入排序就是速度不稳定的算法。

排序稳定性对于基础类型（如 int、double 等）没有任何意义，而对非基础类型则具有重要意义。设想下面两个场景：

  1. 打印整个年级的名册，要求先按班级排序，然后班级内部再按年龄排序，这就要求排序算法具有稳定性。
  2. 你在淘宝上购买商品，如果先将价格从低到高排列，再将评价从高到低排列，那么排在前面的就是物美价廉的商品。

那么哪些排序算法具有稳定性呢？注意，排序稳定性取决于具体实现的细节，例如冒泡排序、选择排序以及归并排序，它们既可以是稳定排序，也可以是不稳定排序，关键取决于你如何处理两个相等的值（把前者仍放前面，后者仍放后面） 。其他排序算法的稳定性见下表。

综合比较

排序 时间复杂度 空间复杂度 稳定性
冒泡排序 O(N^2) O(1) 稳定
选择排序 O(N^2) O(1) 不稳定
插入排序 O(N^2) O(1) 稳定
希尔排序 O(N^2) O(1) 不稳定
归并排序 O(NlogN) O(N) 稳定
堆排序 O(NlogN) O(1) 不稳定
快速排序 O(NlogN) O(logN) 系统栈 不稳定
基数排序 O(N) O(N) 稳定
  • 基于比较的排序，时间复杂度极限为 O(NlogN)O(NlogN)
  • 不基于比较的排序，对数据形式有较大要求，且不适合对象排序
  • 时间复杂度 O(NlogN)O(NlogN) ，空间复杂度 O(N)O(N) ，且稳定的算法是不存在的
  • 随即快排之所以快于归并和堆排序，是因为其常数时间是最小的
  • 追求速度——随即快排，追求空间——堆排序，追求稳定性——归并排序

工程改进

排序算法在工程上的改进可以大致从以下两个角度：

  1. 稳定性

    比如在 java 中的 arrays.sort() 中，当元素是对象时，它会使用归并排序以追求稳定性；当元素是基础类型时，它会使用快速排序以追求速度。

  2. 综合利用

    比如 C 语言中的 std::sort 函数，针对大数据量，使用快排；若快排递归深度超过阈值 __depth_limit ，改用堆排序，防止快排递归过深，同时保持时间复杂度仍是 O(NlogN)；当数据规模小于阈值 _S_threshold 时，改用插入排序，因为插入排序的常数时间小于快排，因此处理小规模数据时更有优势。

速度比较器

速度比较器（自己取的名字，嘿嘿）用来快速比较两种算法的排序速度，由 chatGPT 提供 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <chrono>
#include <random>
#include <functional>
#include "radixSort.h" //引入我们自己写的基数排序
#include <algorithm> //sort
using std::sort;
// 排序函数1
void sortFunc1(int* data, int dataSize) {
    // 在这里实现排序函数1的逻辑
	sort(data, &data[dataSize], [](int a, int b){return a<b;});
}

// 排序函数2
void sortFunc2(int* data, int dataSize) {
    // 在这里实现排序函数2的逻辑
	radixSort(data, dataSize);
}

// 测试排序时间的函数
std::pair<double, double> testSortingTime(std::function<void(int*, int)> sortFunc1,
                                          std::function<void(int*, int)> sortFunc2,
                                          int numComparisons, int dataSize, int maxValue) {
    int* data = new int[dataSize];
    // 生成随机数据
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dis(0, maxValue);
    for (int i = 0; i < dataSize; ++i) {
        data[i] = dis(gen);
    }

    // 测试排序函数1的排序时间
    auto startTime = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < numComparisons; ++i) {
        int* sortedData = new int[dataSize];
        std::copy(data, data + dataSize, sortedData);
        sortFunc1(sortedData, dataSize);
        delete[] sortedData;
    }
    auto endTime = std::chrono::high_resolution_clock::now();
    double sortingTime1 = std::chrono::duration<double>(endTime - startTime).count();

    // 测试排序函数2的排序时间
    startTime = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < numComparisons; ++i) {
        int* sortedData = new int[dataSize];
        std::copy(data, data + dataSize, sortedData);
        sortFunc2(sortedData, dataSize);
        delete[] sortedData;
    }
    endTime = std::chrono::high_resolution_clock::now();
    double sortingTime2 = std::chrono::duration<double>(endTime - startTime).count();

    // 删除动态分配的数组
    delete[] data;

    // 返回排序时间结果
    return std::make_pair(sortingTime1, sortingTime2);
}

int main() {
    // 使用示例：
    auto result = testSortingTime(sortFunc1, sortFunc2, 1, 100000000, 10000000);
    std::cout << "Sorting Time for Function 1: " << result.first << " seconds\n";
    std::cout << "Sorting Time for Function 2: " << result.second << " seconds\n";
    return 0;
}