排序算法

code: sorting_algorithm

1. 问题分析

1.1 问题定义

问题：给定一个包含n个整数的无序数组，将其按升序排列。

示例：

  • 输入：[64, 34, 25, 12, 22, 11, 90]
  • 输出：[11, 12, 22, 25, 34, 64, 90]

1.2 排序算法分类

排序算法可以根据不同的特性进行分类：

按时间复杂度分类：

  • 简单排序：O(n²) - 冒泡排序、插入排序
  • 高效排序：O(n log n) - 快速排序、归并排序、堆排序

按空间复杂度分类：

  • 原地排序：O(1) - 冒泡排序、插入排序、快速排序、堆排序
  • 非原地排序：O(n) - 归并排序

按稳定性分类：

  • 稳定排序：相等元素的相对位置不变 - 冒泡排序、插入排序、归并排序
  • 不稳定排序：相等元素的相对位置可能改变 - 快速排序、堆排序

2. 各算法实现详细解析

2.1 冒泡排序 (BubbleSort)

2.1.1 算法原理

冒泡排序是最基础的排序算法，通过重复遍历数组，比较相邻元素并交换位置，使得较大的元素像”气泡”一样逐渐”浮”到数组末尾。

核心思想：

  1. 从数组开始处遍历，比较相邻的两个元素
  2. 如果前一个元素大于后一个元素，则交换它们的位置
  3. 每轮遍历后，最大的元素会”冒泡”到数组末尾
  4. 重复n-1轮，直到整个数组有序

2.1.2 算法图解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
初始数组: [64, 34, 25, 12, 22]

第1轮: 
[64, 34, 25, 12, 22] → [34, 64, 25, 12, 22] (比较64和34，交换)
[34, 64, 25, 12, 22] → [34, 25, 64, 12, 22] (比较64和25，交换)
[34, 25, 64, 12, 22] → [34, 25, 12, 64, 22] (比较64和12，交换)
[34, 25, 12, 64, 22] → [34, 25, 12, 22, 64] (比较64和22，交换) ✓最大值到位

第2轮:
[34, 25, 12, 22, 64] → [25, 34, 12, 22, 64] (比较34和25，交换)
[25, 34, 12, 22, 64] → [25, 12, 34, 22, 64] (比较34和12，交换)
[25, 12, 34, 22, 64] → [25, 12, 22, 34, 64] (比较34和22，交换) ✓次大值到位

...以此类推

2.1.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void BubbleSort::Sort(std::vector<int32_t> &data)
{
    auto dataSize = std::ssize(data);
    for (std::ptrdiff_t i = 0; i < dataSize - 1; ++i) {
        bool swapped = false;
        // 每轮遍历减少已排序的元素数量
        for (std::ptrdiff_t j = 0; j < dataSize - 1 - i; ++j) {
            if (GetVectorElement(data, j) <= GetVectorElement(data, j + 1)) {
                continue;
            }
            // 交换相邻元素
            std::swap(GetVectorElement(data, j), GetVectorElement(data, j + 1));
            swapped = true;
        }
        // 优化：如果一轮中没有发生交换，说明已经有序
        if (!swapped) {
            break;
        }
    }
}

2.1.4 复杂度分析

  • 时间复杂度：

    • 最好情况：O(n) - 数组已经有序，只需一轮遍历
    • 最坏情况：O(n²) - 数组逆序，需要n(n-1)/2次比较
    • 平均情况：O(n²)

  • 空间复杂度：O(1) - 只需要常数个临时变量

  • 稳定性：✅ 稳定 - 相等元素不会交换位置

  • 适用场景：数据量小或基本有序的情况

2.2 插入排序 (InsertionSort)

2.2.1 算法原理

插入排序的工作方式类似于整理扑克牌：将每张牌插入到已排序的牌中的正确位置。

核心思想：

  1. 将数组分为”已排序区域”和”未排序区域”
  2. 初始时，第一个元素被视为已排序
  3. 从第二个元素开始，依次将每个元素插入到已排序区域的正确位置
  4. 插入时，需要将大于当前元素的已排序元素向后移动

2.2.2 算法图解

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
初始数组: [64, 34, 25, 12, 22]

第1轮: key=34
已排序: [64]
[64, 34, 25, 12, 22] → [34, 64, 25, 12, 22] (34插入到64前面)

第2轮: key=25
已排序: [34, 64]
[34, 64, 25, 12, 22] → [34, 64, 64, 12, 22] (64后移)
                     → [34, 34, 64, 12, 22] (34后移)
                     → [25, 34, 64, 12, 22] (25插入)

第3轮: key=12
已排序: [25, 34, 64]
[25, 34, 64, 12, 22] → [25, 34, 64, 64, 22] (64后移)
                     → [25, 34, 34, 64, 22] (34后移)
                     → [25, 25, 34, 64, 22] (25后移)
                     → [12, 25, 34, 64, 22] (12插入)

第4轮: key=22
已排序: [12, 25, 34, 64]
[12, 25, 34, 64, 22] → [12, 25, 34, 64, 64] (64后移)
                     → [12, 25, 34, 34, 64] (34后移)
                     → [12, 25, 22, 34, 64] (22插入)
                     → [12, 22, 25, 34, 64] (最终结果)

2.2.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InsertionSort::Sort(std::vector<int32_t> &data)
{
    auto dataSize = std::ssize(data);
    for (std::ptrdiff_t i = 0; i < dataSize; ++i) {
        auto key = GetVectorElement(data, i);  // 当前要插入的元素
        auto j = i - 1;
        
        // 将大于key的元素向后移动
        while (j >= 0 && GetVectorElement(data, j) > key) {
            GetVectorElement(data, j + 1) = GetVectorElement(data, j);
            --j;
        }
        // 插入key到正确位置
        GetVectorElement(data, j + 1) = key;
    }
}

2.2.4 复杂度分析

  • 时间复杂度：

    • 最好情况：O(n) - 数组已经有序，每个元素只需比较一次
    • 最坏情况：O(n²) - 数组逆序，需要n(n-1)/2次移动
    • 平均情况：O(n²)

  • 空间复杂度：O(1) - 原地排序

  • 稳定性：✅ 稳定 - 相等元素保持原有顺序

  • 适用场景：

    • 数据量较小
    • 数组基本有序（此时性能接近O(n)）
    • 在线排序（数据陆续到达）

2.3 快速排序 (QuickSort)

2.3.1 算法原理

快速排序采用**分治法(Divide and Conquer)**策略，通过选择一个”基准值(pivot)”，将数组分为两部分：小于基准值的元素和大于基准值的元素，然后递归地对这两部分进行排序。

核心思想：

  1. **选择基准(Pivot)**：从数组中选择一个元素作为基准值
  2. **分区(Partition)**：将数组重新排列，使得：
    • 所有小于基准值的元素都在基准值左边
    • 所有大于基准值的元素都在基准值右边
  3. 递归排序：对基准值左右两个子数组递归应用快速排序
  4. 合并结果：由于是原地排序，不需要额外的合并步骤

2.3.2 分区过程详解

双指针法（本实现采用）：

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
初始数组: [64, 34, 25, 12, 22, 11, 90]
基准值: pivot = 64 (选择最左元素)

初始状态: i=0, j=6
[64, 34, 25, 12, 22, 11, 90]
 ↑                       ↑
 i(pivot)                j

步骤1: 从右向左找第一个 < 64 的元素
[64, 34, 25, 12, 22, 11, 90]
 ↑                   ↑
 i                   j (11 < 64)

步骤2: 从左向右找第一个 > 64 的元素
[64, 34, 25, 12, 22, 11, 90]
 ↑                   ↑
 i(64 > 64? No)     j
 
继续向右，所有元素都 < 64，i和j相遇

步骤3: 交换基准值到最终位置
[11, 34, 25, 12, 22, 64, 90]
                    ↑
                  pivot最终位置

结果: pivot左边都 ≤ 64，右边都 ≥ 64

更复杂的例子：

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
数组: [50, 30, 70, 20, 60, 40, 80]
基准: pivot = 50

初始: i=0, j=6
[50, 30, 70, 20, 60, 40, 80]
 ↑                       ↑
 i                       j

从右找 < 50: j移动到40
[50, 30, 70, 20, 60, 40, 80]
 ↑                   ↑
 i                   j(40 < 50)

从左找 > 50: i移动到70
[50, 30, 70, 20, 60, 40, 80]
         ↑              ↑
         i(70 > 50)     j

交换 i 和 j
[50, 30, 40, 20, 60, 70, 80]
         ↑              ↑
         i              j

从右找 < 50: j移动到20
[50, 30, 40, 20, 60, 70, 80]
             ↑          ↑
             j(20<50)   i

从左找 > 50: i移动到60
[50, 30, 40, 20, 60, 70, 80]
                 ↑  ↑
                 j  i

i >= j，分区结束，交换pivot和j位置
[20, 30, 40, 50, 60, 70, 80]
             ↑
           pivot位置

左子数组: [20, 30, 40]
右子数组: [60, 70, 80]

2.3.3 代码实现

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
void QuickSort::Sort(std::vector<int32_t> &data)
{
    QuickSortRecursive(data, 0, std::ssize(data) - 1);
}

std::ptrdiff_t QuickSort::Partition(std::vector<int32_t> &data, 
                                    std::ptrdiff_t low, 
                                    std::ptrdiff_t high)
{
    // 选择最左元素为基准
    auto pivot = GetVectorElement(data, low);
    auto i = low;
    auto j = high;
    
    while (i < j) {
        // 从右向左找第一个小于pivot的元素
        while (i < j && GetVectorElement(data, j) >= pivot) {
            --j;
        }
        // 从左向右找第一个大于pivot的元素
        while (i < j && GetVectorElement(data, i) <= pivot) {
            ++i;
        }
        // 交换找到的两个元素
        if (i < j) {
            std::swap(GetVectorElement(data, i), GetVectorElement(data, j));
        }
    }
    // 将基准值放到最终位置
    std::swap(GetVectorElement(data, low), GetVectorElement(data, i));
    return i;  // 返回基准值的最终位置
}

void QuickSort::QuickSortRecursive(std::vector<int32_t> &data, 
                                   std::ptrdiff_t low, 
                                   std::ptrdiff_t high)
{
    if (low < high) {
        // 获取基准位置
        auto pivotIndex = Partition(data, low, high);
        // 递归排序左半部分
        QuickSortRecursive(data, low, pivotIndex - 1);
        // 递归排序右半部分
        QuickSortRecursive(data, pivotIndex + 1, high);
    }
}

2.3.4 复杂度分析

  • 时间复杂度：

    • 最好情况：O(n log n) - 每次分区都能均分数组
    • 最坏情况：O(n²) - 数组已排序或逆序，每次只减少一个元素
    • 平均情况：O(n log n)

  • 空间复杂度：

    • O(log n) - 递归栈空间（平均情况）
    • O(n) - 最坏情况的递归深度

  • 稳定性：❌ 不稳定 - 分区交换可能改变相等元素的相对位置

  • 适用场景：

    • 通用排序算法，性能优秀
    • 不需要稳定性的场景
    • 数据量大且随机分布

  • 优化技巧：

    1. 三数取中法选择pivot
    2. 小数组使用插入排序
    3. 三路快排处理大量重复元素

2.4 归并排序 (MergeSort)

2.4.1 算法原理

归并排序同样采用分治法，但与快速排序不同，它的核心在于”合并”而非”分区”。

核心思想：

  1. **分解(Divide)**：将数组不断二分，直到每个子数组只有一个元素
  2. **合并(Merge)**：将两个有序的子数组合并成一个有序数组
  3. 递归执行：自底向上逐层合并，最终得到完全有序的数组

关键洞察：

  • 单个元素天然有序
  • 合并两个有序数组是简单的O(n)操作
  • 通过递归合并，最终整个数组有序

2.4.2 算法图解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
初始数组: [64, 34, 25, 12, 22, 11, 90, 88]

【分解阶段 - 自顶向下】
                [64, 34, 25, 12, 22, 11, 90, 88]
                          ↓ 分割
        [64, 34, 25, 12]           [22, 11, 90, 88]
              ↓ 分割                      ↓ 分割
    [64, 34]    [25, 12]          [22, 11]    [90, 88]
      ↓ 分割      ↓ 分割            ↓ 分割      ↓ 分割
   [64] [34]   [25] [12]         [22] [11]   [90] [88]
    
【合并阶段 - 自底向上】
第1层合并（单个元素合并）:
   [64] + [34] → [34, 64]
   [25] + [12] → [12, 25]
   [22] + [11] → [11, 22]
   [90] + [88] → [88, 90]

第2层合并（2元素数组合并）:
   [34, 64] + [12, 25] → [12, 25, 34, 64]
   [11, 22] + [88, 90] → [11, 22, 88, 90]

第3层合并（4元素数组合并）:
   [12, 25, 34, 64] + [11, 22, 88, 90] → [11, 12, 22, 25, 34, 64, 88, 90]

2.4.3 合并过程详解

双指针合并法：

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
合并两个有序数组: left=[12, 25, 34]  right=[11, 22, 64]

初始状态:
left:  [12, 25, 34]    right: [11, 22, 64]    temp: []
        ↑                      ↑
        i                      j

步骤1: 比较12和11，11较小
temp: [11]
left:  [12, 25, 34]    right: [11, 22, 64]
        ↑                          ↑
        i                          j

步骤2: 比较12和22，12较小
temp: [11, 12]
left:  [12, 25, 34]    right: [11, 22, 64]
            ↑                      ↑
            i                      j

步骤3: 比较25和22，22较小
temp: [11, 12, 22]
left:  [12, 25, 34]    right: [11, 22, 64]
            ↑                          ↑
            i                          j

步骤4: 比较25和64，25较小
temp: [11, 12, 22, 25]
left:  [12, 25, 34]    right: [11, 22, 64]
                ↑                      ↑
                i                      j

步骤5: 比较34和64，34较小
temp: [11, 12, 22, 25, 34]
left:  [12, 25, 34]    right: [11, 22, 64]
                   ↑                   ↑
                (越界)                  j

步骤6: left已空，复制right剩余元素
temp: [11, 12, 22, 25, 34, 64]

最终结果: [11, 12, 22, 25, 34, 64]

2.4.4 代码实现

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
void MergeSort::Sort(std::vector<int32_t> &data)
{
    MergeSortRecursive(data, 0, std::ssize(data) - 1);
}

void MergeSort::MergeSortRecursive(std::vector<int32_t> &data, 
                                   std::ptrdiff_t left, 
                                   std::ptrdiff_t right)
{
    // 基线条件：只有一个元素时停止递归
    if (left >= right) {
        return;
    }

    // 计算中间位置（防止溢出）
    auto mid = left + (right - left) / 2;
    
    // 递归排序左半部分
    MergeSortRecursive(data, left, mid);
    
    // 递归排序右半部分
    MergeSortRecursive(data, mid + 1, right);
    
    // 合并两个有序子数组
    Merge(data, left, mid, right);
}

void MergeSort::Merge(std::vector<int32_t> &data, 
                      std::ptrdiff_t left, 
                      std::ptrdiff_t mid, 
                      std::ptrdiff_t right)
{
    // 创建临时数组
    std::vector<int32_t> temp(static_cast<size_t>(right - left + 1));
    
    auto i = left;          // 左子数组起始索引
    auto j = mid + 1;       // 右子数组起始索引
    std::ptrdiff_t k = 0;   // 临时数组索引

    // 合并两个有序数组
    while (i <= mid && j <= right) {
        if (GetVectorElement(data, i) <= GetVectorElement(data, j)) {
            GetVectorElement(temp, k++) = GetVectorElement(data, i++);
        } else {
            GetVectorElement(temp, k++) = GetVectorElement(data, j++);
        }
    }

    // 复制左子数组剩余元素
    while (i <= mid) {
        GetVectorElement(temp, k++) = GetVectorElement(data, i++);
    }

    // 复制右子数组剩余元素
    while (j <= right) {
        GetVectorElement(temp, k++) = GetVectorElement(data, j++);
    }

    // 将临时数组的结果复制回原数组
    for (std::ptrdiff_t p = 0; p < std::ssize(temp); ++p) {
        GetVectorElement(data, (left + p)) = GetVectorElement(temp, p);
    }
}

2.4.5 复杂度分析

  • 时间复杂度：

    • 最好情况：O(n log n)
    • 最坏情况：O(n log n)
    • 平均情况：O(n log n)
    • **稳定的O(n log n)**：无论什么情况都是这个复杂度

  • 空间复杂度：O(n) - 需要额外的临时数组

  • 稳定性：✅ 稳定 - 合并时相等元素保持原有顺序

  • 递归深度：O(log n)

  • 适用场景：

    • 需要稳定排序的场景
    • 数据量大且对空间要求不严格
    • 外部排序（处理大文件）
    • 链表排序（可以O(1)空间）

2.5 堆排序 (HeapifySort)

2.5.1 算法原理

堆排序利用**堆(Heap)**这种数据结构进行排序。堆是一个完全二叉树，分为最大堆和最小堆。

堆的性质：

  • 最大堆：每个节点的值都大于或等于其子节点的值（根节点是最大值）
  • 最小堆：每个节点的值都小于或等于其子节点的值（根节点是最小值）

核心思想（使用最大堆升序排序）：

  1. 构建最大堆：将无序数组调整为最大堆
  2. 堆顶与末尾交换：将堆顶（最大值）与数组末尾交换
  3. 重新堆化：对剩余元素重新调整为最大堆
  4. 重复步骤2-3：直到所有元素都排序完成

2.5.2 堆的数组表示

在数组中表示完全二叉树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
数组索引: [0, 1, 2, 3, 4, 5, 6]
数组值:   [90, 70, 60, 30, 50, 20, 40]

对应的树结构:
           90(0)
          /      \
       70(1)     60(2)
      /    \     /    \
   30(3) 50(4) 20(5) 40(6)

索引关系:
- 父节点: i
- 左子节点: 2*i + 1
- 右子节点: 2*i + 2
- 父节点索引: (i-1) / 2

2.5.3 堆化(Heapify)过程详解

堆化：将以某个节点为根的子树调整为最大堆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
例子: 对索引i=1进行堆化

原始状态:
           90(0)
          /      \
       30(1)     60(2)
      /    \     /    \
   70(3) 50(4) 20(5) 40(6)

步骤1: 找出节点1、左子节点3、右子节点4中的最大值
   30(1): 值30
   70(3): 值70 ← 最大
   50(4): 值50
   
步骤2: 交换节点1和节点3
           90(0)
          /      \
       70(1)     60(2)
      /    \     /    \
   30(3) 50(4) 20(5) 40(6)

步骤3: 递归对节点3进行堆化（已经是叶子节点，结束）

最终结果: 以节点1为根的子树现在是最大堆

完整的堆排序过程：

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, 34, 25, 12, 22, 11, 90]

【第一阶段：构建最大堆】

步骤1: 从最后一个非叶子节点开始（索引n/2-1）
数组索引7个元素，最后非叶子节点 = 7/2-1 = 2

堆化索引2 (值25):
           64
          /   \
        34     25
       /  \   /  \
     12   22 11  90
     
左子: 11, 右子: 90 → 90最大，交换
           64
          /   \
        34     90
       /  \   /  \
     12   22 11  25

堆化索引1 (值34):
左子: 12, 右子: 22 → 34最大，不交换

堆化索引0 (值64):
左子: 34, 右子: 90 → 90最大，交换
           90
          /   \
        34     64
       /  \   /  \
     12   22 11  25
     
继续堆化索引2 (值64):
左子: 11, 右子: 25 → 64最大，不交换

最大堆构建完成: [90, 34, 64, 12, 22, 11, 25]

【第二阶段：排序】

迭代1: 交换堆顶90和末尾25
[25, 34, 64, 12, 22, 11 | 90]
堆化索引0，得到: [64, 34, 25, 12, 22, 11 | 90]

迭代2: 交换堆顶64和末尾11
[11, 34, 25, 12, 22 | 64, 90]
堆化索引0，得到: [34, 22, 25, 12, 11 | 64, 90]

迭代3: 交换堆顶34和末尾11
[11, 22, 25, 12 | 34, 64, 90]
堆化索引0，得到: [25, 22, 11, 12 | 34, 64, 90]

迭代4: 交换堆顶25和末尾12
[12, 22, 11 | 25, 34, 64, 90]
堆化索引0，得到: [22, 12, 11 | 25, 34, 64, 90]

迭代5: 交换堆顶22和末尾11
[11, 12 | 22, 25, 34, 64, 90]
堆化索引0，得到: [12, 11 | 22, 25, 34, 64, 90]

迭代6: 交换堆顶12和末尾11
[11 | 12, 22, 25, 34, 64, 90]

最终结果: [11, 12, 22, 25, 34, 64, 90] ✓

2.5.4 代码实现

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
void HeapifySort::Sort(std::vector<int32_t> &data)
{
    auto dataSize = std::ssize(data);
    
    // 第一阶段：构建最大堆
    // 从最后一个非叶子节点开始，逐个向前进行堆化
    for (std::ptrdiff_t i = dataSize / 2 - 1; i >= 0; --i) {
        Heapify(data, dataSize, i);
    }
    
    // 第二阶段：排序
    // 依次将堆顶（最大值）与末尾交换，然后重新堆化
    for (std::ptrdiff_t i = dataSize - 1; i > 0; --i) {
        // 将当前最大值（堆顶）移到数组末尾
        std::swap(GetVectorElement(data, 0), GetVectorElement(data, i));
        
        // 对剩余元素重新堆化
        Heapify(data, i, 0);
    }
}

void HeapifySort::Heapify(std::vector<int32_t> &data, 
                          std::ptrdiff_t n,   // 堆的大小
                          std::ptrdiff_t i)   // 要堆化的节点索引
{
    auto largest = i;         // 初始化最大值为当前节点
    auto left = 2 * i + 1;    // 左子节点索引
    auto right = 2 * i + 2;   // 右子节点索引

    // 如果左子节点存在且大于当前最大值
    if (left < n && GetVectorElement(data, left) > GetVectorElement(data, largest)) {
        largest = left;
    }

    // 如果右子节点存在且大于当前最大值
    if (right < n && GetVectorElement(data, right) > GetVectorElement(data, largest)) {
        largest = right;
    }

    // 如果最大值不是当前节点，则交换并递归堆化
    if (largest != i) {
        std::swap(GetVectorElement(data, i), GetVectorElement(data, largest));
        
        // 递归堆化受影响的子树
        Heapify(data, n, largest);
    }
}

2.5.5 复杂度分析

  • 时间复杂度：

    • 构建堆：O(n)
    • 排序：O(n log n)
    • 总体：O(n log n)（所有情况都相同）

  • 空间复杂度：O(1) - 原地排序（递归栈深度O(log n)）

  • 稳定性：❌ 不稳定 - 堆化过程中会改变相等元素的相对位置

  • 适用场景：

    • 需要O(n log n)保证且空间受限
    • Top-K问题（找最大/最小的K个元素）
    • 优先队列的实现

3. 算法性能对比

3.1 时间复杂度对比

算法 最好情况 平均情况 最坏情况 备注
冒泡排序 O(n) O(n²) O(n²) 优化版可提前终止
插入排序 O(n) O(n²) O(n²) 小数组或基本有序时很快
快速排序 O(n logn) O(n log n) O(n²) 平均性能最好
归并排序 O(n logn) O(n log n) O(n log n) 性能稳定
堆排序 O(n logn) O(n log n) O(n log n) 不受数据分布影响

3.2 空间复杂度对比

算法 空间复杂度 是否原地排序
冒泡排序 O(1) ✅ 是
插入排序 O(1) ✅ 是
快速排序 O(log n) ✅ 是
归并排序 O(n) ❌ 否
堆排序 O(1) ✅ 是

3.3 稳定性对比

算法 稳定性 说明
冒泡排序 ✅ 稳定 相邻元素比较，不会改变相对位置
插入排序 ✅ 稳定 向前插入时保持相对顺序
快速排序 ❌ 不稳定 分区交换可能打乱相对位置
归并排序 ✅ 稳定 合并时可以保持相对顺序
堆排序 ❌ 不稳定 堆化过程会打乱相对位置

3.4 实际性能测试

基于不同数据规模的性能对比（仅供参考）：

**小数据量 (n < 50)**：

  1. 插入排序 - 最快（缓存友好，常数小）
  2. 冒泡排序（优化版）
  3. 快速排序、归并排序、堆排序（递归开销大）

**中等数据量 (50 < n < 10000)**：

  1. 快速排序 - 通常最快
  2. 堆排序
  3. 归并排序
  4. 插入排序
  5. 冒泡排序

**大数据量 (n > 10000)**：

  1. 快速排序 - 平均最快
  2. 归并排序 - 稳定且可预测
  3. 堆排序 - 空间优势
  4. 插入排序、冒泡排序 - 不适用

4. 算法选择指南

4.1 根据需求选择

需求场景 推荐算法 理由
数据量小（< 50） 插入排序 实现简单，性能好
数据基本有序 插入排序 时间复杂度接近O(n)
需要稳定排序 归并排序 唯一稳定的O(n log n)算法
空间受限 堆排序 原地排序，O(1)空间
通用场景，追求平均性能 快速排序 平均性能最优
需要可预测的性能 归并排序/堆排序 所有情况都是O(n log n)
在线排序（数据陆续到达） 插入排序 可以高效处理新数据
Top-K问题 堆排序 只需要部分有序

4.2 实际应用建议

生产环境推荐：

  • C++ STL std::sort：混合算法（快排+插入排序+堆排序）
  • Java Arrays.sort：
    • 基本类型：双轴快速排序
    • 对象类型：TimSort（归并+插入的混合）
  • **Python sorted()**：TimSort

混合策略：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void HybridSort(std::vector<int> &data) {
    if (data.size() < 10) {
        // 小数组用插入排序
        InsertionSort(data);
    } else {
        // 大数组用快速排序
        QuickSort(data);
        
        // 如果递归深度过深，切换到堆排序
        if (depth > 2 * log2(data.size())) {
            HeapSort(data);
        }
    }
}

5. 核心概念总结

5.1 分治法(Divide and Conquer)

快速排序、归并排序、堆排序都使用了分治思想：

  1. **分解(Divide)**：将问题分解为子问题
  2. **解决(Conquer)**：递归解决子问题
  3. **合并(Combine)**：合并子问题的解

区别：

  • 快速排序：分解复杂（分区），合并简单（无需操作）
  • 归并排序：分解简单（二分），合并复杂（需要合并操作）
  • 堆排序：利用堆结构，每次提取最大值

5.2 稳定性的重要性

稳定性在某些场景很重要：

1
2
3
4
5
6
7
8
9
// 学生记录
struct Student {
    string name;
    int score;
    int id;  // 注册顺序
};

// 先按成绩排序，再按ID排序
// 如果排序算法不稳定，相同成绩的学生ID顺序可能被打乱

5.3 原地排序的意义

原地排序在以下场景重要：

  • 嵌入式系统（内存受限）
  • 大数据处理（减少内存占用）
  • 实时系统（避免内存分配）

6. 扩展知识

6.1 其他排序算法

  • 希尔排序：插入排序的改进，O(n^1.3)
  • 计数排序：O(n+k)，适用于整数且范围小
  • 桶排序：O(n+k)，将数据分布到多个桶中
  • 基数排序：O(d(n+k))，按位排序

6.2 下界证明

基于比较的排序算法理论下界是**O(n log n)**：

  • 决策树模型证明
  • n个元素有n!种排列
  • log₂(n!) ≈ n log n

非比较排序（计数、桶、基数）可以突破这个下界。

6.3 工程实践

实际生产中的排序通常是混合算法：

Introsort（STL中的实现）：

  1. 主要使用快速排序
  2. 递归深度过深时切换到堆排序（避免O(n²)）
  3. 小数组使用插入排序（减少递归开销）

这种混合方式综合了各算法的优点，达到了最佳的实际性能。