📚 课程目录第2章基础排序算法选型

2. 基础排序算法选型：冒泡排序、插入排序、快速排序对比与适用场景

在场景地图的节点优先级排序中，选择合适的排序算法直接影响地图构建的实时性与稳定性。本章从原理、实现流程、代码实例、调试部署、常见错误及性能优化等维度，横向对比冒泡排序、插入排序和快速排序，帮助你在不同数据规模与分布下做出正确选型。

2.1 算法原理与核心思想

算法	核心思想	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	相邻元素两两比较，较大元素“冒泡”到数组末端	O(n²)	O(n²)	O(1)	稳定
插入排序	将未排序元素插入已排序部分的正确位置	O(n²)	O(n²)	O(1)	稳定
快速排序	选取基准，将数组分成小于和大于基准的两部分，递归排序	O(n log n)	O(n²)	O(log n)~O(n)	不稳定

2.2 场景地图节点优先级的特征

节点规模：多数情况下在 10～5000 之间（小到中型地图）。
优先级分布：大部分节点优先级接近，偶尔出现极高或极低异常值。
动态更新：部分场景需要频繁插入/删除节点（如实时导航）。
稳定性需求：当优先级相同时，通常希望保持节点原始录入顺序（稳定排序）。

选型建议：若节点数少于 100 且预期分布较为随机，插入排序因常数低、对局部有序数据表现优异而占优；若节点数超过 1000 且对实时性要求高，快速排序（配合随机基准）是最佳选择；冒泡排序仅在教学或极端小规模（如 < 50）场景下使用，不推荐工程实践。

2.3 实现流程与代码示例

冒泡排序实现流程

从索引 0 到 n-2 遍历，比较相邻元素；
若前一个优先级大于后一个，则交换位置；
每轮结束后最大元素被移至末尾；
重复 n-1 轮，或某一轮无交换提前终止。

// 冒泡排序（场景地图节点优先级数组 int pri[]）
void bubbleSort(int pri[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; ++j) {
            if (pri[j] > pri[j + 1]) {
                std::swap(pri[j], pri[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

插入排序实现流程

从索引 1 开始，标记当前待插入元素 key；
将 key 与其左侧已排序元素从右向左比较；
若左侧元素大于 key，则将左侧元素右移一位；
找到合适位置后插入 key，重复至数组末尾。

// 插入排序（节点优先级数组）
void insertionSort(int pri[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = pri[i];
        int j = i - 1;
        while (j >= 0 && pri[j] > key) {
            pri[j + 1] = pri[j];
            --j;
        }
        pri[j + 1] = key;
    }
}

快速排序实现流程

选取基准（建议随机选或取中位数）；
使用双指针（或单指针）将数组划分为 < 基准、基准、≥ 基准三部分；
递归对左右子区间执行相同过程；
当子区间长度 ≤ 1 时返回。

// 快速排序（随机基准，递归版）
void quickSort(int pri[], int left, int right) {
    if (left >= right) return;
    int pivotIndex = left + rand() % (right - left + 1);
    std::swap(pri[pivotIndex], pri[left]);   // 将基准移到最左
    int pivot = pri[left];
    int i = left, j = right;
    while (i < j) {
        while (i < j && pri[j] >= pivot) --j;
        pri[i] = pri[j];
        while (i < j && pri[i] <= pivot) ++i;
        pri[j] = pri[i];
    }
    pri[i] = pivot;
    quickSort(pri, left, i - 1);
    quickSort(pri, i + 1, right);
}

2.4 调试与部署要点

边界测试：空数组、单元素、已有序数组、逆序数组、所有优先级相等的数组。
日志辅助：在排序前后打印前 10 个节点优先级，验证排序正确性。
性能观测：使用 std::chrono 或 clock() 记录排序耗时，插入排序处理有序数据时速度优于快速排序。
稳定性验证：对优先级相同的节点，记录其原始索引，排序后检查顺序是否保留。

常见错误 1 – 快速排序递归过深导致栈溢出：当数据规模大且接近有序时，若未采用随机基准或三数取中，递归深度可能达到 O(n)。解决方法：1) 对小于阈值（如 16）的子区间改用插入排序；2) 设置递归深度限制并转为迭代实现。

  常见错误 2 – 冒泡排序未利用提前终止优化：很多实现会遗漏 swapped 标志，导致即便数组已有序仍会执行完整的 n-1 轮。务必加入该优化，使最佳情况时间复杂度降为 O(n)。

2.5 性能与稳定性优化

优化点	冒泡排序	插入排序	快速排序
提前终止	✅ 可用	❌ 不适用	❌ 不适用
局部有序加速	❌ 效果弱	✅ 效果显著	✅ 混合插入排序
随机化基准	❌ 不适用	❌ 不适用	✅ 强烈推荐
三路划分（重复元素）	❌	❌	✅ 减少递归
尾递归优化	❌	❌	✅ 可编译器优化

2.6 选型决策流程图

2.7 工程实践建议

在场景地图模块中，将排序算法封装为策略类（Strategy Pattern），运行时根据节点规模动态切换算法。
对于实时更新频繁的场景（如SLAM中的动态节点），考虑使用插入排序维护局部有序性，或结合二分查找定位插入位置。
快速排序在关键系统中建议使用std::sort（内省排序），它综合了快速排序、堆排序和插入排序的优点，能避免所有最坏情况。
若节点数大于 10000，应优先使用堆排序或归并排序（稳定）——这部分将在后续章节讨论。