C++怎么实现一个快速排序算法_C++经典排序算法与QuickSort代码详解-C++-PHP中文网

C++怎么实现一个快速排序算法_C++经典排序算法与QuickSort代码详解

冰火之心

发布： 2025-11-21 17:51:06

原创

892人浏览过

快速排序采用分治策略，通过分区操作将数组分为两部分并递归排序。选择基准元素后，用双指针法重排数组，使左侧元素小于等于基准，右侧大于基准，基准置于正确位置。常用Lomuto分区方案以末尾元素为基准，通过交换实现分区，返回基准位置供递归使用。完整代码包含partition和quickSort函数，主函数演示了排序过程。优化方法包括随机化基准、三数取中、小数组改用插入排序及尾递归优化，提升性能与稳定性。C++标准库的std::sort结合快排、堆排和插排，适应多种数据场景。

c++怎么实现一个快速排序算法_c++经典排序算法与quicksort代码详解

快速排序是一种高效的排序算法，采用分治策略来把一个序列分成两个子序列。它的平均时间复杂度为 O(n log n)，在实际应用中表现优秀，是 C++ 中常用的排序方法之一。下面详细介绍快速排序的实现原理和完整代码。

快速排序的基本思想

快速排序的核心是“分区”（partition）操作。从数组中选择一个基准元素（pivot），然后将数组中小于基准的元素移到左边，大于基准的元素移到右边，基准放在中间。这个过程完成后，基准元素的位置就是它在最终有序数组中的位置。接着对左右两个子数组递归执行相同的操作。

关键步骤包括：

选择一个基准值（通常选首元素、尾元素或中间元素）
重新排列数组，使小于基准的在左，大于的在右
递归地对左右子数组进行快排

分区操作的实现方式

常见的分区方法是使用双指针法。以下是以最后一个元素为基准的 Lomuto 分区方案：

立即学习“C++免费学习笔记（深入）”；

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 基准
    int i = low - 1;       // 小于基准区域的边界
<pre class='brush:php;toolbar:false;'>for (int j = low; j < high; j++) {
    if (arr[j] <= pivot) {
        i++;
        std::swap(arr[i], arr[j]);
    }
}
std::swap(arr[i + 1], arr[high]);
return i + 1;

登录后复制

}

MagicStudio

图片处理必备效率神器！为你的图片提供神奇魔法

102

查看详情

该函数返回基准元素的最终位置，便于后续递归调用划分区间。

完整的快速排序代码

结合递归函数，可以写出完整的快速排序实现：

#include <iostream>
<p>void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}</p><p>// 使用示例
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);</p><pre class='brush:php;toolbar:false;'>quickSort(arr, 0, n - 1);

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

return 0;

登录后复制

}