c++中如何实现快速排序算法_快排算法原理与C++代码实现

快速排序通过分治法实现高效排序，核心是选择基准并分区。1. 选末尾元素为基准，用partition函数将小于等于基准的移到左边，大于的移到右边，并返回基准正确位置；2. 递归对左右子数组调用quickSort；3. C++代码实现包括partition、quickSort和打印函数；4. 示例展示排序前后的数组变化；5. 优化建议含随机化基准、三数取中、小数组用插入排序及尾递归优化。掌握partition是关键。

快速排序是一种高效的排序算法，采用分治策略来把一个序列分成两个子序列，然后递归排序。它的平均时间复杂度为 O(n log n)，在实际应用中表现优异。

快排算法基本原理

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

具体步骤如下：

• 从数组中选择一个元素作为基准（通常选第一个、最后一个或中间元素）
• 重新排列数组，使所有小于基准的元素位于其左侧，大于等于的位于右侧
• 对左右两个子数组分别递归调用快排

C++代码实现

下面是一个简洁且高效的C++实现版本，使用最右边的元素作为基准：

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

#include <iostream>
#include <vector>
<p>// 分区函数：将数组按基准划分
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[high]; // 以最后一个元素为基准
int i = low - 1;       // 小于基准的区域的边界</p><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; // 返回基准的索引

}

算家云

高效、便捷的人工智能算力服务平台

37

查看详情

// 快速排序主函数 void quickSort(std::vector<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); // 排序基准右边
}

}

// 打印数组 void printArray(const std::vector<int>& arr) { for (int val : arr) std::cout << val << " "; std::cout << std::endl; }

使用示例：

int main() {
    std::vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();
<pre class='brush:php;toolbar:false;'>std::cout << "排序前: ";
printArray(arr);

quickSort(arr, 0, n - 1);

std::cout << "排序后: ";
printArray(arr);

return 0;

优化建议与注意事项

虽然上述实现清晰易懂，但在实际使用中可考虑以下几点优化：

• 随机化基准：避免最坏情况（如已排序数组），可随机选择基准并与其末尾元素交换
• 三数取中法：取首、中、尾三个元素的中位数作为基准
• 小数组改用插入排序：当子数组长度小于10时，插入排序更高效
• 尾递归优化：先处理较小的子数组，减少栈深度

基本上就这些。快速排序理解起来不难，关键在于分区逻辑的正确实现和递归边界的控制。写好 partition 函数，整个算法就成功了一大半。

以上就是c++++中如何实现快速排序算法_快排算法原理与C++代码实现的详细内容，更多请关注php中文网其它相关文章！