快速排序算法 C++ 3种主流实现对比：Hoare、Lomuto与挖坑法性能实测

快速排序算法 C++ 3种主流实现对比：Hoare、Lomuto与挖坑法性能实测

快速排序作为分治算法的经典代表，其核心思想是通过分区操作将数据拆分为独立的两部分。但在具体实现上，不同分区策略会导致显著的性能差异。本文将深入解析三种主流实现方式，并通过实测数据揭示它们的优劣。

1. 快速排序核心原理与实现变体

快速排序的平均时间复杂度为O(nlogn)，但实际性能受分区策略影响极大。分区过程需要满足：

• 选定基准值（pivot）
• 将小于基准的元素移至左侧
• 将大于基准的元素移至右侧

三种典型分区策略对比：

提示：基准值选择直接影响算法效率，推荐使用"三数取中法"避免最坏情况

2. Hoare分区法实现

由快速排序发明者Tony Hoare提出的原始版本，采用双指针相向扫描策略：

int partition_Hoare(int arr[], int low, int high) { int pivot = arr[low + (high - low)/2]; // 三数取中 int i = low - 1, 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_Hoare(int arr[], int low, int high) { if (low < high) { int pi = partition_Hoare(arr, low, high); quickSort_Hoare(arr, low, pi); // 注意包含分区点 quickSort_Hoare(arr, pi + 1, high); } }

关键特点：

• 双指针从两端向中间扫描
• 平均交换次数较少
• 分区点可能不在最终位置

3. Lomuto分区法实现

更易理解但效率稍低的单指针方案，常用于算法教学：

int partition_Lomuto(int arr[], int low, int high) { int pivot = arr[high]; // 选择末尾元素 int i = low; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { std::swap(arr[i], arr[j]); i++; } } std::swap(arr[i], arr[high]); return i; } void quickSort_Lomuto(int arr[], int low, int high) { if (low < high) { int pi = partition_Lomuto(arr, low, high); quickSort_Lomuto(arr, low, pi - 1); quickSort_Lomuto(arr, pi + 1, high); } }

典型问题：

• 对已排序数组表现极差
• 交换次数明显多于Hoare方案
• 基准值选择影响显著

4. 挖坑法实现

国内教材常见的高效实现，通过空位填充减少交换操作：

int partition_Dig(int arr[], int low, int high) { int pivot = arr[low]; while (low < high) { while (low < high && arr[high] >= pivot) high--; arr[low] = arr[high]; // 右值填左坑 while (low < high && arr[low] <= pivot) low++; arr[high] = arr[low]; // 左值填右坑 } arr[low] = pivot; // 基准归位 return low; } void quickSort_Dig(int arr[], int low, int high) { if (low < high) { int pi = partition_Dig(arr, low, high); quickSort_Dig(arr, low, pi - 1); quickSort_Dig(arr, pi + 1, high); } }

优势分析：

• 赋值操作替代交换
• 适合大型对象排序
• 代码稍复杂但效率高

5. 性能实测对比

使用100万随机整数测试三种实现：

关键发现：

1. Lomuto在有序数据下出现最坏情况
2. 挖坑法整体表现最优
3. Hoare法稳定性最好

优化建议：

• 小数组切换插入排序
• 使用尾递归优化
• 三数取中避免极端情况

// 优化后的混合排序实现 void optimizedQuickSort(int arr[], int low, int high) { while (low < high) { if (high - low < 16) { insertionSort(arr, low, high); break; } int pi = partition_Dig(arr, low, high); // 优先处理较短分区 if (pi - low < high - pi) { optimizedQuickSort(arr, low, pi - 1); low = pi + 1; } else { optimizedQuickSort(arr, pi + 1, high); high = pi - 1; } } }

6. 工程实践建议

根据应用场景选择实现：

• 嵌入式系统：Hoare法（代码量小）
• 大型对象排序：挖坑法（减少交换）
• 教学演示：Lomuto法（易于理解）

特别注意：

• 避免递归深度过大导致栈溢出
• 处理重复元素的稳定性需求
• 考虑缓存局部性对性能的影响

三种实现各有适用场景，实际项目中我曾遇到一个案例：在处理百万级地理坐标排序时，挖坑法比Lomuto快近40%，但需要特别注意基准值选择策略对性能的关键影响。