本文还有配套的精品资源，点击获取 menu-r.4af5f7ec.gif

简介：排序算法是计算机科学中的基础内容，本文重点介绍了冒泡排序、快速排序和堆排序三种经典算法，并基于C++语言进行了实现。冒泡排序以简单直观著称，适合小规模数据；快速排序采用分治策略，平均性能优异；堆排序基于树形结构，具有稳定的O(n log n)时间复杂度。文章附带Sort.h和heap.h源码文件，支持自定义比较规则，便于灵活应用与学习。通过本项目，可深入理解算法原理、时间复杂度及实际编码技巧。

1. 排序算法概述

排序算法是计算机科学中最基础且广泛应用的算法之一，其核心目标是将一组无序的数据按照特定规则（如升序或降序）进行排列。排序不仅提升了数据的可读性，更为后续的查找、统计与分析操作提供了高效基础。排序算法种类繁多，根据其实现机制可分为 比较类排序 （如快速排序、归并排序）与 非比较类排序 （如计数排序、基数排序）。不同算法在时间复杂度、空间复杂度、稳定性等方面各有优劣，适用于不同的数据规模和应用场景。掌握排序算法的基本原理，是深入算法学习与工程实践的重要起点。

2. 冒泡排序原理与C++实现

冒泡排序（Bubble Sort）是一种基础且直观的排序算法，它通过重复遍历待排序的序列，比较相邻的两个元素，并根据比较结果交换它们的位置，从而将较大的元素逐渐“浮”到序列的末端，形象地称之为“冒泡”。尽管冒泡排序在实际工程中由于其较低的效率并不常用，但它却是理解排序算法思想、掌握算法设计与实现技巧的重要入门工具。

2.1 冒泡排序的基本思想

冒泡排序之所以得名，是因为它的工作方式类似于水中的气泡上升：在每一轮排序过程中，较大的元素会像气泡一样“浮”到数组的末尾。这种排序方式的核心在于相邻元素的比较与交换机制，它通过多次遍历数组，将每个未排序部分中的最大值逐步“推”到正确的位置。

2.1.1 算法流程概述

冒泡排序的基本流程可以分为以下几个步骤：

  1. 初始化 ：设定一个未排序的数组。
  2. 遍历数组 ：从数组的第一个元素开始，依次比较相邻的两个元素。
  3. 比较与交换 ：如果前一个元素大于后一个元素（默认升序），则交换两者的位置。
  4. 一轮排序结束 ：当一轮遍历结束后，最大的元素会移动到数组的末尾。
  5. 缩小排序范围 ：将下一轮排序的范围缩小一个元素（即不再处理已排序部分）。
  6. 重复过程 ：重复上述步骤，直到所有元素有序为止。

这一流程可以通过一个简单的流程图来展示其执行逻辑：

graph TD
    A[开始] --> B[初始化数组]
    B --> C{遍历次数 < n-1 ?}
    C -- 是 --> D[遍历数组]
    D --> E{当前元素 > 下一个元素 ?}
    E -- 是 --> F[交换位置]
    E -- 否 --> G[继续下一对]
    D --> H[标记已排序末尾]
    H --> I[遍历次数+1]
    I --> C
    C -- 否 --> J[结束]

2.1.2 相邻元素比较与交换机制

冒泡排序的关键在于其比较与交换机制。这一机制的实现依赖于数组的索引访问与临时变量的使用。以下是一个简单的代码片段，演示了如何在数组中实现相邻元素的比较与交换：

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换相邻元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
代码逐行分析：
  • 第1行 ：定义一个函数 bubbleSort ，接受一个整型数组 arr 和其长度 n 。
  • 第2行 ：外层循环控制排序的轮数，共进行 n-1 轮。
  • 第3行 ：内层循环用于遍历当前未排序部分的元素，每轮减少一个已排序元素。
  • 第4行 ：判断当前元素是否大于下一个元素，若成立则进行交换。
  • 第5-7行 ：使用临时变量 temp 完成交换操作，确保数据不丢失。

这种机制确保了每一轮排序都将当前未排序部分的最大值“冒”到最后一个位置，从而实现整体有序。

2.2 冒泡排序的C++代码实现

冒泡排序的实现可以分为两个版本：基本版本和优化版本。基本版本按照上述流程实现，而优化版本则通过提前终止机制来提升效率。

2.2.1 基本版本的实现逻辑

基本版本的冒泡排序是严格按照算法流程实现的，它不考虑任何优化策略，每轮都会遍历整个未排序部分并进行比较与交换。以下是完整的实现代码：

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    cout << "Sorted array: \n";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}
代码逻辑分析：
  • 主函数部分 ：定义了一个待排序的数组 arr ，并通过 sizeof 运算获取数组长度 n 。
  • 调用排序函数 ：调用 bubbleSort 对数组进行排序。
  • 输出排序结果 ：使用 cout 输出排序后的数组。

2.2.2 优化版本（提前终止机制）

为了提升冒泡排序的效率，可以引入“提前终止”的优化机制。即在某一轮排序中如果没有发生任何交换操作，说明数组已经有序，可以提前结束排序。

void optimizedBubbleSort(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}
优化机制说明：
  • swapped 标志位 ：用于标记当前轮是否有交换发生。
  • 提前终止条件 ：如果某一轮没有发生交换（即 swapped == false ），则说明数组已经有序，跳出循环。
  • swap 函数 ：C++标准库提供的交换函数，比手动交换更简洁高效。
对比分析：
版本 是否优化 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度
基本版 否 O(n²) O(n²) O(1)
优化版 是 O(n²) O(n) O(1)

可以看到，优化版本在数组本身已经有序时能够将时间复杂度降低至 O(n)，从而显著提升效率。

2.3 冒泡排序的优缺点与适用场景

冒泡排序虽然简单，但其效率不高，因此在实际开发中应用较少。不过，它仍然具有教学价值和特定场景的实用性。

2.3.1 时间复杂度分析

冒泡排序的时间复杂度取决于数组的初始状态：

  • 最坏情况 ：数组完全逆序，此时每一轮都要进行 n-i-1 次比较和交换，总比较次数为 n(n-1)/2 ，时间复杂度为 O(n²) 。
  • 最好情况 ：数组已经有序，此时只需一轮遍历即可终止排序，比较次数为 n-1 ，时间复杂度为 O(n) 。
  • 平均情况 ：假设数据是随机排列的，平均比较次数为 n²/2 ，时间复杂度仍为 O(n²) 。
数据状态 时间复杂度
已排序 O(n)
随机 O(n²)
逆序 O(n²)

2.3.2 稳定性与空间复杂度探讨

  • 稳定性 ：冒泡排序是稳定的排序算法。稳定性是指在排序过程中，相同元素的相对顺序不会被改变。由于冒泡排序仅在相邻元素不满足顺序时才交换，因此相同元素不会被交换位置。
  • 空间复杂度 ：冒泡排序仅需要常数级别的额外空间（如临时变量），因此其空间复杂度为 O(1) ，属于原地排序算法。

2.3.3 适用场景举例（小规模数据排序）

尽管冒泡排序效率不高，但在以下场景中仍然可以使用：

  1. 教学用途 ：帮助初学者理解排序思想和算法流程。
  2. 小规模数据集 ：对于少量数据（如几十个元素），冒泡排序的效率与其它排序算法相差不大。
  3. 嵌入式系统 ：在内存受限的环境中，冒泡排序因其原地排序特性而适用。
示例：对10个整数进行排序
int smallData[] = {5, 1, 4, 2, 8, 0, 3, 7, 6, 9};
int size = sizeof(smallData) / sizeof(smallData[0]);

optimizedBubbleSort(smallData, size);

// 输出结果：0 1 2 3 4 5 6 7 8 9
应用场景分析：
  • 嵌入式设备排序 ：例如传感器采集的数据排序。
  • 调试工具排序 ：作为快速验证排序逻辑的工具。
  • 教学演示 ：展示排序过程与算法执行步骤。

冒泡排序作为一种基础排序算法，虽然在实际工程中并不常用，但其原理清晰、实现简单，是学习排序算法的良好起点。下一章将介绍更为高效的快速排序算法，敬请期待。

3. 快速排序原理与C++实现

3.1 快速排序的核心思想

3.1.1 分治策略的基本原理

快速排序（Quick Sort）是一种基于 分治法 （Divide and Conquer）思想的排序算法。其基本原理是将一个大问题划分为若干个子问题，分别求解后再将子问题的解合并，从而得到原问题的解。具体到快速排序中，其分治策略的体现如下：

  1. 划分（Partition） ：从数组中选择一个基准元素（pivot），将数组划分为两个子数组：一个包含所有小于等于基准值的元素，另一个包含所有大于基准值的元素。
  2. 递归（Recursive） ：对两个子数组分别递归执行上述划分过程，直到子数组的长度为1或0时终止递归。
  3. 合并（Combine） ：由于划分过程中已经将元素按大小关系排列，因此无需额外合并操作。

这种分治策略的优势在于，它通过每次划分将问题规模缩小为原来的约一半，从而在平均情况下达到 O(n log n) 的时间复杂度。

3.1.2 基准值的选择与划分过程

基准值（Pivot）的选择策略

基准值的选择对快速排序的性能有显著影响。常见的选择策略包括：

选择策略 描述
固定位置选择 通常选择第一个、最后一个或中间元素作为基准。简单但可能退化
随机选择 在数组中随机选择一个元素作为基准。避免最坏情况
三数取中法 选取首、尾、中间三个元素的中位数作为基准。减少极端情况影响
划分过程（Partition）详解

划分是快速排序的核心操作，其目的是将数组分为两部分，使得左侧元素 ≤ pivot，右侧元素 > pivot（或反之）。常见的划分方法有：

  • Hoare分区 ：使用双指针从两端向中间扫描，交换逆序元素。
  • Lomuto分区 ：单向扫描，维护一个边界指针i，将小于等于pivot的元素移动到i左侧。
  • 三向切分 ：适用于存在大量重复元素的数据集，将数组分为小于、等于、大于三部分。

以下展示一种典型的Hoare分区实现：

int partition(int arr[], int low, int high) {
    int pivot = arr[low]; // 选取第一个元素作为基准
    int i = low - 1;
    int j = high + 1;

    while (true) {
        do {
            i++;
        } while (arr[i] < pivot); // 找到大于等于基准的元素

        do {
            j--;
        } while (arr[j] > pivot); // 找到小于等于基准的元素

        if (i >= j) return j; // 划分完成

        std::swap(arr[i], arr[j]); // 交换逆序元素
    }
}

逐行逻辑分析 ：

  • int pivot = arr[low]; ：选择第一个元素作为基准值。
  • int i = low - 1; int j = high + 1; ：初始化两个指针，分别从数组两端向内移动。
  • do { i++; } while (arr[i] < pivot); ：i向右移动，直到找到一个大于等于pivot的元素。
  • do { j--; } while (arr[j] > pivot); ：j向左移动，直到找到一个小于等于pivot的元素。
  • if (i >= j) return j; ：当两个指针相遇或交叉，说明划分完成。
  • std::swap(arr[i], arr[j]); ：交换两个逆序元素，使它们回到正确的一侧。

该划分方式的优点是效率高，尤其在数据分布较为随机时表现良好。

3.2 快速排序的C++实现细节

3.2.1 递归实现方式

快速排序的递归实现非常直观，主要分为两个函数： quickSort 用于递归调用， partition 用于划分数组。

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // 获取划分点
        quickSort(arr, low, pi);             // 排序左半部分
        quickSort(arr, pi + 1, high);        // 排序右半部分
    }
}

逐行逻辑分析 ：

  • if (low < high) ：递归终止条件，当子数组长度为1或0时停止。
  • int pi = partition(arr, low, high); ：调用划分函数，获取划分点位置。
  • quickSort(arr, low, pi); ：递归排序左半部分（小于等于pivot的部分）。
  • quickSort(arr, pi + 1, high); ：递归排序右半部分（大于pivot的部分）。

完整示例 ：

#include <iostream>
#include <algorithm>

int partition(int arr[], int low, int high) {
    int pivot = arr[low];
    int i = low - 1;
    int j = high + 1;

    while (true) {
        do i++; while (arr[i] < pivot);
        do j--; while (arr[j] > pivot);
        if (i >= j) return j;
        std::swap(arr[i], arr[j]);
    }
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);

    std::cout << "Sorted array: \n";
    for (int i = 0; i < n; i++) std::cout << arr[i] << " ";
    std::cout << std::endl;
    return 0;
}

输出结果 ：

Sorted array: 
1 5 7 8 9 10

3.2.2 非递归实现方式（使用栈）

为了减少递归带来的栈溢出风险，可以采用 显式栈 （如C++中的 std::stack ）模拟递归过程。

#include <iostream>
#include <stack>

int partition(int arr[], int low, int high) {
    int pivot = arr[low];
    int i = low - 1;
    int j = high + 1;

    while (true) {
        do i++; while (arr[i] < pivot);
        do j--; while (arr[j] > pivot);
        if (i >= j) return j;
        std::swap(arr[i], arr[j]);
    }
}

void quickSortIterative(int arr[], int low, int high) {
    std::stack<std::pair<int, int>> stack;
    stack.push({low, high});

    while (!stack.empty()) {
        std::pair<int, int> current = stack.top();
        stack.pop();
        low = current.first;
        high = current.second;

        if (low < high) {
            int pi = partition(arr, low, high);
            stack.push({pi + 1, high});  // 右半部分入栈
            stack.push({low, pi});       // 左半部分入栈
        }
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSortIterative(arr, 0, n - 1);

    std::cout << "Sorted array: \n";
    for (int i = 0; i < n; i++) std::cout << arr[i] << " ";
    std::cout << std::endl;
    return 0;
}

逐行逻辑分析 ：

  • std::stack<std::pair<int, int>> stack; ：使用栈来模拟递归调用。
  • stack.push({low, high}); ：将初始范围压入栈中。
  • while (!stack.empty()) ：循环处理栈中的每一个子数组范围。
  • std::pair<int, int> current = stack.top(); stack.pop(); ：取出当前处理范围。
  • stack.push({pi + 1, high}); 和 stack.push({low, pi}); ：将左右子数组范围压入栈中，模拟递归调用顺序。

流程图展示 ：

graph TD
A[开始] --> B[初始化栈]
B --> C[将(low, high)压入栈]
C --> D{栈是否为空?}
D -- 否 --> E[取出栈顶元素]
E --> F[执行划分操作]
F --> G[得到划分点pi]
G --> H[将右子数组压栈]
H --> I[将左子数组压栈]
I --> D
D -- 是 --> J[排序完成]

3.3 快速排序的性能分析与优化

3.3.1 时间复杂度与空间复杂度分析

情况 时间复杂度 空间复杂度 说明
最好情况 O(n log n) O(log n) 每次划分平衡，递归深度为log n
平均情况 O(n log n) O(log n) 数据分布随机，划分平均
最坏情况 O(n²) O(n) 数据已有序或逆序，每次划分极不平衡

3.3.2 随机化基准值提升性能

为避免最坏情况发生，可以采用随机选择基准值的方式：

int partitionRandom(int arr[], int low, int high) {
    srand(time(0));
    int random = low + rand() % (high - low + 1);
    std::swap(arr[low], arr[random]); // 将随机选中的元素交换到第一个位置
    return partition(arr, low, high);
}

逐行逻辑分析 ：

  • srand(time(0)); ：初始化随机种子。
  • int random = low + rand() % (high - low + 1); ：生成一个low到high之间的随机索引。
  • std::swap(arr[low], arr[random]); ：将随机选中的元素交换到第一个位置，以便后续调用原 partition 函数。
  • return partition(arr, low, high); ：调用标准划分函数。

这样可以有效避免输入数据已有序导致的最坏时间复杂度问题。

3.3.3 与归并排序的对比（适用大规模数据）

特性 快速排序 归并排序
时间复杂度 O(n log n) 平均 O(n log n) 稳定
空间复杂度 O(log n)（原地排序） O(n)（需要额外空间）
是否稳定 否 是
是否原地排序 是 否
适用场景 内存敏感，大数据排序 外部排序、链表排序

快速排序在内存使用效率和实际运行速度上优于归并排序，尤其适用于 大规模数据排序 。然而，在需要稳定排序或处理链表结构时，归并排序更具优势。

总结 ：
本章详细介绍了快速排序的 分治思想 、 划分机制 、 递归与非递归实现方式 ，并通过 性能分析 和 优化策略 展示了其在实际编程中的优势与应用场景。同时，通过与归并排序的对比，帮助开发者在不同场景下选择合适的排序算法。

4. 堆排序原理与C++实现

堆排序（Heap Sort）是一种基于完全二叉树结构的比较排序算法，其核心思想是利用最大堆（或最小堆）的特性来完成排序过程。堆排序具有原地排序、时间复杂度稳定为 $ O(n \log n) $ 的优势，因此在系统资源受限或数据量较大的场景中具有广泛的应用价值。本章将从堆的定义出发，深入剖析堆排序的实现机制，并通过C++代码演示其完整实现与优化方式。

4.1 堆排序的理论基础

堆排序的实现依赖于一种称为“堆”的数据结构，它是一种特殊的完全二叉树结构，具有堆序性。堆排序通常使用最大堆来实现升序排序。

4.1.1 二叉堆的定义与性质

二叉堆（Binary Heap） 是一种近似完全二叉树的数据结构，满足以下两个性质：

  1. 堆序性（Heap Property） ：
    - 最大堆：任意父节点的值 ≥ 子节点的值；
    - 最小堆：任意父节点的值 ≤ 子节点的值。
  2. 完全二叉树结构 ：
    - 堆可以用数组来实现，索引从0开始，左孩子为 2*i + 1 ，右孩子为 2*i + 2 ，父节点为 (i - 1) / 2 。

以下是一个最大堆的示意图：

graph TD
    A[90] --> B[70]
    A --> C[50]
    B --> D[40]
    B --> E[30]
    C --> F[20]

该结构中，每个父节点的值都大于其子节点，符合最大堆的特性。

4.1.2 建堆与堆调整过程

堆排序的第一步是构建最大堆，随后反复执行“堆调整”操作。

  • 建堆（Build Heap） ：
    从最后一个非叶子节点（即索引为 n/2 - 1 的节点）开始向上调整，确保每个子树都满足最大堆的性质。

  • 堆调整（Heapify） ：
    对某个节点，如果其值小于其子节点，则将其与较大的子节点交换，并递归调整被交换后的子树。

堆调整示例代码（C++）：
void heapify(int arr[], int n, int i) {
    int largest = i;          // 当前节点
    int left = 2 * i + 1;     // 左孩子
    int right = 2 * i + 2;    // 右孩子

    // 如果左孩子大于当前最大值
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 如果右孩子大于当前最大值
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果最大值不是当前节点，交换并继续调整
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest); // 递归调整受影响的子树
    }
}

逐行解读：

  • largest = i ：假设当前节点是最大的；
  • left = 2 * i + 1 和 right = 2 * i + 2 是二叉树中子节点的索引；
  • 比较左右子节点与当前节点的值，更新最大值；
  • 若最大值不是当前节点，则交换并递归向下调整，以保证堆性质的恢复。

4.2 堆排序的实现步骤

堆排序的完整流程可以分为两个阶段： 建堆 和 排序 。

4.2.1 构建最大堆

构建最大堆的核心在于从最后一个非叶子节点开始，依次向上执行 heapify 操作。例如，对于长度为 n 的数组，最后一个非叶子节点的索引为 n/2 - 1 。

构建最大堆的C++实现：
void buildMaxHeap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
}

逐行解读：

  • i = n / 2 - 1 ：从最后一个非叶子节点开始；
  • heapify(arr, n, i) ：逐层向上调整，保证整个数组满足最大堆的性质。

4.2.2 堆排序的具体执行流程

堆排序的执行流程如下：

  1. 将数组构造成最大堆；
  2. 将堆顶元素（最大值）与末尾元素交换；
  3. 忽略末尾元素，重新调整堆顶元素以恢复堆的性质；
  4. 重复步骤2-3，直到所有元素排序完成。
堆排序C++代码实现：
void heapSort(int arr[], int n) {
    buildMaxHeap(arr, n); // 构建最大堆

    // 逐个取出最大元素并调整堆
    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]); // 将最大值移到末尾
        heapify(arr, i, 0);   // 调整堆顶元素
    }
}

逐行解读：

  • buildMaxHeap(arr, n) ：构建初始最大堆；
  • swap(arr[0], arr[i]) ：将当前堆顶（最大值）交换到末尾；
  • heapify(arr, i, 0) ：对剩余的堆（长度为 i ）进行堆调整，确保堆性质。

4.3 堆排序的C++代码实现与优化

本节将给出完整的堆排序C++实现代码，并探讨其性能优化策略与在Top K问题中的应用。

4.3.1 基础实现版本

完整的堆排序程序如下，包含主函数用于测试：

#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void buildMaxHeap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
}

void heapSort(int arr[], int n) {
    buildMaxHeap(arr, n);

    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

// 测试代码
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "原始数组：";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;

    heapSort(arr, n);

    cout << "排序后数组：";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

4.3.2 性能优化与边界情况处理

虽然堆排序的时间复杂度为 $ O(n \log n) $，但在实际应用中仍有优化空间：

优化方向 说明
小数组优化 对于长度小于某个阈值（如16）的数组，改用插入排序提升性能
堆调整优化 使用循环代替递归，避免栈溢出，提高执行效率
多线程处理 对大规模数据可尝试并行化堆构建与排序
使用循环实现堆调整（避免递归）：
void heapifyIterative(int arr[], int n, int i) {
    while (i < n) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest])
            largest = left;

        if (right < n && arr[right] > arr[largest])
            largest = right;

        if (largest == i) break;

        swap(arr[i], arr[largest]);
        i = largest;
    }
}

4.3.3 堆排序在Top K问题中的应用

堆排序在处理 Top K 问题 时具有天然优势，尤其是使用最小堆来找出最大的 K 个数。

Top K 问题实现思路：
  1. 使用一个大小为 K 的最小堆；
  2. 遍历数组，将前 K 个元素加入堆；
  3. 对于后续每个元素，若大于堆顶（当前堆中最小元素），则替换堆顶并调整堆；
  4. 遍历结束后，堆中保存的就是最大的 K 个元素。
Top K 问题 C++ 实现（最小堆）：
#include <iostream>
#include <vector>
using namespace std;

void minHeapify(vector<int>& heap, int n, int i) {
    while (i < n) {
        int smallest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && heap[left] < heap[smallest])
            smallest = left;

        if (right < n && heap[right] < heap[smallest])
            smallest = right;

        if (smallest == i) break;

        swap(heap[i], heap[smallest]);
        i = smallest;
    }
}

vector<int> findTopK(vector<int>& nums, int k) {
    vector<int> heap(nums.begin(), nums.begin() + k);
    for (int i = k / 2 - 1; i >= 0; i--)
        minHeapify(heap, k, i);

    for (int i = k; i < nums.size(); i++) {
        if (nums[i] > heap[0]) {
            heap[0] = nums[i];
            minHeapify(heap, k, 0);
        }
    }

    return heap;
}

int main() {
    vector<int> nums = {3, 2, 1, 5, 6, 4};
    int k = 3;

    vector<int> topK = findTopK(nums, k);
    cout << "Top " << k << " 元素为：";
    for (int num : topK) cout << num << " ";
    cout << endl;

    return 0;
}

输出： 

Top 3 元素为：4 5 6

该方法时间复杂度为 $ O(n \log k) $，空间复杂度为 $ O(k) $，适用于大数据流中查找 Top K 元素的场景。

本章详细介绍了堆排序的基本原理、实现流程及其在C++中的具体实现，并通过Top K问题展示了其实际应用价值。堆排序以其稳定的 $ O(n \log n) $ 时间复杂度和原地排序的优势，成为排序算法中不可或缺的重要成员。

5. 排序算法时间复杂度分析

排序算法的效率是衡量其优劣的重要指标，本章将系统地分析冒泡排序、快速排序和堆排序的时间复杂度。通过大O表示法，对比不同算法在不同输入规模下的性能表现，并讨论其在最坏、最好和平均情况下的运行时间差异，为算法选择提供理论依据。

5.1 时间复杂度的基本概念与表示方法

5.1.1 时间复杂度定义与大O表示法

时间复杂度是衡量一个算法执行效率的重要标准，它描述了算法运行时间与输入数据规模之间的增长关系。通常我们使用大O表示法（Big O notation）来表示算法的最坏情况时间复杂度。

大O表示法的形式为：
T(n) = O(f(n))
$$
其中 $ T(n) $ 表示算法在输入规模为 $ n $ 时的运行时间，$ f(n) $ 是一个与运行时间增长速率相关的函数。它忽略常数项和低阶项，只关注最高阶项的增长趋势。

例如，若一个算法的时间复杂度为 $ T(n) = 3n^2 + 2n + 1 $，则其大O表示为 $ O(n^2) $。

5.1.2 最好、最坏与平均时间复杂度

在分析排序算法时，我们通常需要考虑三种时间复杂度：

  • 最好情况时间复杂度 ：当输入数据已经有序时，算法所需的最少运行时间。
  • 最坏情况时间复杂度 ：当输入数据为最不利排列时，算法所需的最长运行时间。
  • 平均情况时间复杂度 ：在所有可能的输入数据排列中，算法运行时间的期望值。

这些复杂度帮助我们理解算法在不同场景下的表现，并为实际应用提供选择依据。

5.1.3 复杂度分析的意义与作用

通过时间复杂度分析，我们可以：

  • 预测算法在不同数据规模下的执行效率。
  • 比较不同算法的性能差异。
  • 评估算法是否适合特定的应用场景。

例如，在处理大规模数据时，选择一个平均时间复杂度为 $ O(n \log n) $ 的排序算法（如快速排序或堆排序）将比 $ O(n^2) $ 的冒泡排序更高效。

5.2 冒泡排序的时间复杂度分析

5.2.1 基本冒泡排序的最坏情况分析

冒泡排序是一种简单的排序算法，其基本思想是通过多次遍历数组，每次将相邻的两个元素进行比较并交换位置，最终将最大值“冒泡”到末尾。

最坏情况 发生在输入数组为 逆序 时。例如：

int arr[] = {5, 4, 3, 2, 1};

在最坏情况下，冒泡排序需要进行 $ n-1 $ 轮比较，每轮比较次数递减，总共比较次数为：

\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}

因此，冒泡排序的最坏时间复杂度为 $ O(n^2) $。

5.2.2 优化冒泡排序的最好情况分析

在数组 已经有序 的情况下，冒泡排序的最好情况时间复杂度为 $ O(n) $。这是因为我们可以设置一个标志变量 swapped ，用于检测是否发生交换，如果没有交换，则提前终止排序。

优化版本的冒泡排序伪代码如下：

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

逻辑分析 ：
- 外层循环控制排序轮数（最多 $ n-1 $ 轮）。
- 内层循环进行相邻元素比较与交换，最多 $ n-i-1 $ 次。
- 若某一轮未发生交换（即 swapped == false ），说明数组已有序，提前退出。

参数说明 ：
- arr[] ：待排序的整型数组。
- n ：数组长度。
- swapped ：用于判断是否发生交换的布尔变量。

5.2.3 平均时间复杂度与性能评估

在随机排列的数据中，冒泡排序的平均时间复杂度为 $ O(n^2) $。虽然它在小规模数据中表现尚可，但随着数据量增加，其性能迅速下降，因此不适用于大规模排序任务。

5.3 快速排序的时间复杂度分析

5.3.1 快速排序的分治策略与递归结构

快速排序基于分治策略（Divide and Conquer），其基本思想是：

  1. 选择基准值 （pivot）。
  2. 划分数组 ：将小于基准值的元素放在左侧，大于基准值的元素放在右侧。
  3. 递归处理左右子数组 。

快速排序的递归结构如下图所示：

graph TD
    A[QuickSort(arr, low, high)] --> B{low < high}
    B -->|是| C[Partition(arr, low, high)]
    C --> D[QuickSort(left)]
    C --> E[QuickSort(right)]
    B -->|否| F[终止递归]

5.3.2 最坏、最好与平均时间复杂度分析

最坏情况 ：当每次划分都将数组划分为一个长度为0和一个长度为 $ n-1 $ 的子数组时（例如输入数组已有序），快速排序的时间复杂度为：

T(n) = T(n-1) + O(n) = O(n^2)

最好情况 ：当每次划分都将数组划分为两个大小相等的子数组时，快速排序的时间复杂度为：

T(n) = 2T\left(\frac{n}{2}\right) + O(n) = O(n \log n)

平均情况 ：假设每次划分的基准值选择是随机的，则平均时间复杂度为：

T(n) = O(n \log n)

5.3.3 基准值选择对性能的影响

基准值的选择对快速排序的性能影响巨大。常见的选择方式包括：

基准值选择方式 优点 缺点 时间复杂度
固定选择（如第一个元素） 简单 易导致最坏情况 $ O(n^2) $
随机选择 提高平均性能 稍微增加随机数开销 $ O(n \log n) $
三数取中（median-of-three） 减少最坏情况出现概率 实现稍复杂 $ O(n \log n) $

通过使用随机化或三数取中策略，可以显著提升快速排序在实际应用中的性能。

5.4 堆排序的时间复杂度分析

5.4.1 堆排序的基本流程与时间构成

堆排序利用 二叉堆 结构进行排序，主要分为两个阶段：

  1. 建堆 ：将无序数组构造成一个最大堆（或最小堆）。
  2. 排序 ：反复从堆中取出最大元素（堆顶），并调整堆结构。

堆排序的时间复杂度主要由以下部分构成：

  • 建堆操作 ：$ O(n) $
  • 堆调整（Heapify） ：每次调整的时间为 $ O(\log n) $，共执行 $ n-1 $ 次。

因此，堆排序的总时间复杂度为：

T(n) = O(n) + (n - 1) \cdot O(\log n) = O(n \log n)

5.4.2 堆排序的稳定性与空间复杂度

  • 时间复杂度 ：始终为 $ O(n \log n) $，无论输入数据的初始状态如何。
  • 空间复杂度 ：$ O(1) $，属于原地排序算法。
  • 稳定性 ： 不稳定排序 ，因为在交换过程中可能改变相同元素的相对顺序。

5.4.3 堆排序与快速排序的对比

指标 堆排序 快速排序
时间复杂度（平均） $ O(n \log n) $ $ O(n \log n) $
时间复杂度（最坏） $ O(n \log n) $ $ O(n^2) $
空间复杂度 $ O(1) $ $ O(\log n) $（递归栈）
稳定性 不稳定 不稳定
适用场景 适用于需要稳定性能的大规模排序 适用于数据分布随机、追求平均性能

堆排序在最坏情况下的性能优于快速排序，因此在对性能要求较高的系统中（如嵌入式系统或实时系统）更为可靠。

5.5 综合对比与选择建议

5.5.1 排序算法时间复杂度对比表

排序算法 最好情况 平均情况 最坏情况 空间复杂度 稳定性
冒泡排序 $ O(n) $ $ O(n^2) $ $ O(n^2) $ $ O(1) $ 稳定
快速排序 $ O(n \log n) $ $ O(n \log n) $ $ O(n^2) $ $ O(\log n) $ 不稳定
堆排序 $ O(n \log n) $ $ O(n \log n) $ $ O(n \log n) $ $ O(1) $ 不稳定

5.5.2 不同场景下的排序算法选择建议

应用场景 推荐算法 理由
小规模数据排序 冒泡排序 简单易实现，适合教学和小数据量场景
数据基本有序 快速排序（随机化基准） 平均性能好，且能避免最坏情况
数据完全无序 快速排序 / 堆排序 快速排序平均性能最佳，堆排序最坏性能稳定
数据量极大 堆排序 保证最坏情况下仍为 $ O(n \log n) $
嵌入式系统 / 实时系统 堆排序 空间占用低，性能稳定
数据重复多且需稳定排序 冒泡排序 稳定性保障，但效率较低

5.5.3 性能优化策略与实践建议

  1. 混合排序策略 ：结合多种排序算法的优点，例如在递归深度较小时使用插入排序优化快速排序。
  2. 三数取中法 ：在快速排序中选择基准值时使用三数取中法以避免最坏情况。
  3. 尾递归优化 ：在递归实现快速排序时，减少递归栈的使用。
  4. 原地排序 ：优先选择空间复杂度低的排序算法，尤其在内存受限的环境下。

通过本章的深入分析，我们系统地了解了冒泡排序、快速排序和堆排序在不同输入情况下的时间复杂度表现，并结合实际应用场景给出了选择建议与优化策略。下一章将围绕排序算法的自定义比较规则展开，进一步提升排序的灵活性与适用性。

6. 自定义比较规则实现

在实际的编程实践中，排序算法的应用远不止于对数字的升序或降序排列。很多时候，我们需要根据特定的业务逻辑对数据进行排序，这就需要自定义比较规则的支持。C++标准库提供了灵活的机制，允许开发者根据需求自定义排序规则，从而实现更复杂、更贴近实际需求的排序逻辑。

6.1 排序中比较规则的作用

6.1.1 默认排序规则的局限性

在C++中，标准库函数如 std::sort 默认使用 < 运算符进行排序。这种默认方式适用于基本数据类型（如 int 、 float ）和部分标准库容器。然而，当处理自定义类型（如结构体或类）时，默认排序规则往往无法满足业务需求。

例如，考虑一个表示学生的结构体：

struct Student {
    std::string name;
    int age;
    float score;
};

如果我们希望按成绩排序，而不是默认的成员比较，就需要自定义比较规则。

6.1.2 自定义比较器的必要性

自定义比较器允许我们定义任意两个元素之间的比较逻辑。它不仅提高了排序的灵活性，还能帮助我们实现复杂的排序逻辑，如多字段排序、逆序排序等。

6.2 C++中自定义比较函数的实现方式

6.2.1 函数指针与仿函数的使用

C++支持通过函数指针或仿函数（函数对象）来传递自定义比较逻辑。

使用函数指针
bool compareByScore(const Student& a, const Student& b) {
    return a.score < b.score;
}

std::vector<Student> students = {/* 初始化数据 */};
std::sort(students.begin(), students.end(), compareByScore);

上述代码定义了一个比较函数 compareByScore ，并将其作为第三个参数传递给 std::sort 。

使用仿函数（函数对象）
struct CompareByAge {
    bool operator()(const Student& a, const Student& b) const {
        return a.age < b.age;
    }
};

std::sort(students.begin(), students.end(), CompareByAge());

仿函数允许在类中封装比较逻辑，适用于需要状态或更复杂逻辑的场景。

6.2.2 Lambda表达式在排序中的应用

C++11引入的Lambda表达式极大简化了自定义比较器的编写：

std::sort(students.begin(), students.end(), 
    [](const Student& a, const Student& b) {
        return a.name < b.name;
    });

以上代码使用Lambda表达式按姓名排序，语法简洁，适合一次性使用的比较逻辑。

6.3 自定义排序规则的典型应用场景

6.3.1 复合数据类型的排序

在处理结构体或类对象时，自定义比较器是必须的。例如，按年龄升序排序：

std::sort(students.begin(), students.end(), 
    [](const Student& a, const Student& b) {
        return a.age < b.age;
    });

6.3.2 多字段排序与稳定性控制

有时候需要按多个字段排序。例如，先按成绩降序，再按年龄升序：

std::sort(students.begin(), students.end(), 
    [](const Student& a, const Student& b) {
        if (a.score != b.score)
            return a.score > b.score; // 成绩降序
        return a.age < b.age; // 年龄升序
    });

通过在比较函数中添加逻辑判断，可以实现多字段排序。同时，如果使用 std::stable_sort ，可以保持相同元素的原始顺序，实现稳定性控制。

6.3.3 实际项目中灵活排序的实现技巧

在实际项目开发中，排序逻辑可能频繁变化。为提高灵活性，可以将比较逻辑抽象为接口或策略模式。例如：

using CompareFunc = std::function<bool(const Student&, const Student&)>;

void sortStudents(std::vector<Student>& students, CompareFunc cmp) {
    std::sort(students.begin(), students.end(), cmp);
}

// 调用示例
sortStudents(students, [](const Student& a, const Student& b) {
    return a.score > b.score;
});

通过函数对象传递比较逻辑，可以实现排序逻辑的解耦与复用，提升代码可维护性。

（未完待续）

本文还有配套的精品资源，点击获取 menu-r.4af5f7ec.gif

简介：排序算法是计算机科学中的基础内容，本文重点介绍了冒泡排序、快速排序和堆排序三种经典算法，并基于C++语言进行了实现。冒泡排序以简单直观著称，适合小规模数据；快速排序采用分治策略，平均性能优异；堆排序基于树形结构，具有稳定的O(n log n)时间复杂度。文章附带Sort.h和heap.h源码文件，支持自定义比较规则，便于灵活应用与学习。通过本项目，可深入理解算法原理、时间复杂度及实际编码技巧。


本文还有配套的精品资源，点击获取
menu-r.4af5f7ec.gif

Logo
亚马逊云科技技术品牌专区

更多推荐

cover

同声语音翻译-即时语音翻译-语音互译-语音实时翻译API接口介绍

avatar 亚马逊云科技技术品牌专区
cover

工业5G专网UPF下沉架构与边缘网关设备接入协议解析实践

avatar 亚马逊云科技技术品牌专区

合肥沛文智能科技有限公司做GEO的核心优势

合肥沛文智能科技有限公司是国内，在GEO这一新兴赛道上拥有显著的先发优势。当前生成式AI正在从根本上重构用户获取商业信息的路径。截至2026年，国内AI搜索日活用户已突破8亿，超过65%的消费购买决策与B端采购评估以AI问答结果作为首要参考依据。用户行为已从“打开浏览器搜索”转变为“直接向AI提问”——“哪个品牌口碑更好”“哪家服务商性价比高”，由AI整合信息后给出最终推荐。在这一范式迁移中，沛文

avatar 亚马逊云科技技术品牌专区