- C++
C++ 快速排序
- 2025-6-9 22:59:15 @
快速排序基本概念
快速排序(QuickSort)是由英国计算机科学家Tony Hoare在1960年提出的一种高效排序算法,它采用分治法(Divide and Conquer)策略。快速排序的基本思想是:
- 选择基准值(Pivot):从数组中选择一个元素作为基准值。
- 分区操作(Partition):将数组中的元素重新排列,使得所有小于基准值的元素放在基准值的左边,所有大于基准值的元素放在基准值的右边。这个过程称为分区(Partitioning)。
- 递归排序子数组:对基准值左右两侧的子数组分别递归地应用快速排序。
快速排序的平均时间复杂度为O(n log n),最坏情况下为O(n²),但通过合理选择基准值(如三数取中法),可以有效避免最坏情况的发生。它是一种原地排序算法(不需要额外的存储空间),因此在实际应用中非常高效。
快速排序的C++实现
下面是一个用C++实现的快速排序算法,包含详细的注释:
#include <iostream>
#include <vector>
using namespace std;
// 分区函数:将数组的一部分进行分区,返回基准值的最终位置
int partition(vector<int>& arr, int low, int high) {
// 选择最后一个元素作为基准值
int pivot = arr[high];
// i 指向当前小于基准值的元素序列的末尾
int i = low - 1;
// 遍历从 low 到 high-1 的所有元素
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于基准值
if (arr[j] < pivot) {
// i 向前移动一位
i++;
// 交换 arr[i] 和 arr[j]
swap(arr[i], arr[j]);
}
}
// 将基准值放到正确的位置
swap(arr[i + 1], arr[high]);
// 返回基准值的位置
return (i + 1);
}
// 快速排序函数:对数组的 [low, high] 区间进行排序
void quickSort(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 vector<int>& arr) {
for (int num : arr) {
cout << num << " ";
}
cout << endl;
}
int main() {
// 测试数据
vector<int> arr = {10, 7, 8, 9, 1, 5};
cout << "原始数组: ";
printArray(arr);
// 调用快速排序
quickSort(arr, 0, arr.size() - 1);
cout << "排序后的数组: ";
printArray(arr);
return 0;
}
代码解释
-
partition函数:
- 该函数选择最后一个元素作为基准值(pivot)。
- 使用变量
i
来跟踪小于基准值的元素应该放置的位置。 - 遍历数组,将所有小于基准值的元素交换到左边。
- 最后将基准值放到正确的位置,并返回该位置。
-
quickSort函数:
- 递归地对数组进行排序。
- 如果
low
小于high
,说明子数组中至少有两个元素,需要继续排序。 - 通过调用
partition
函数获取基准值的位置,然后分别对左右两部分递归排序。
-
main函数:
- 创建测试数组并打印原始数据。
- 调用
quickSort
函数进行排序。 - 打印排序后的结果。
快速排序示例
让我们通过一个简单的例子来演示快速排序的工作过程。假设我们有一个数组:[5, 3, 8, 4, 2]
-
选择基准值:选择最后一个元素
2
作为基准值。 -
分区操作:
- 遍历数组:
5
大于2
,不交换;3
大于2
,不交换;8
大于2
,不交换;4
大于2
,不交换。 - 最后将基准值
2
与第一个大于它的元素5
交换,得到:[2, 3, 8, 4, 5]
。 - 基准值
2
的最终位置是索引0
。
- 遍历数组:
-
递归排序子数组:
- 左子数组:
[]
,无需排序。 - 右子数组:
[3, 8, 4, 5]
,继续排序。
- 左子数组:
对于右子数组[3, 8, 4, 5]
:
- 选择基准值
5
。 - 分区后得到:
[3, 4, 5, 8]
。 - 递归排序左子数组
[3, 4]
和右子数组[8]
。
最终得到排序后的数组:[2, 3, 4, 5, 8]
。
快速排序的优化
虽然上面的实现很直观,但在实际应用中,我们可以通过以下方法优化快速排序:
-
随机选择基准值:避免最坏情况的发生,提高算法的稳定性。
-
三数取中法:选择数组的第一个、中间和最后一个元素的中间值作为基准值,进一步减少最坏情况的概率。
-
小数组使用插入排序:对于小规模数组,插入排序的性能更好,可以在子数组较小时切换到插入排序。
-
三路快排:将数组分为小于、等于和大于基准值三部分,处理包含大量重复元素的数据时效率更高。
快速排序是一种非常灵活的算法,通过不同的优化策略,可以适应各种不同的应用场景。
3 条评论
-
admin SU @ 2025-6-16 20:35:57
将快速排序中的分区逻辑从
arr[j] > pivot
改为arr[j] >= pivot
确实有区别,但两种实现都是正确的。它们的主要区别在于处理重复元素的方式和性能表现。核心区别
-
右指针
j
的终止条件:- 原代码(
arr[j] > pivot
):j
会停在第一个 ≤ pivot 的元素上。 - 修改后(
arr[j] >= pivot
):j
会跳过所有 = pivot 的元素,直到遇到 < pivot 的元素或与i
交叉。
- 原代码(
-
重复元素的分布:
- 原代码:重复的
pivot
值可能被分散到左右两部分。 - 修改后:更多重复的
pivot
值会被集中到左半部分(基准值最终的左侧)。
- 原代码:重复的
正确性分析
两种实现都能正确排序的原因:
- 分区的本质:快速排序的核心是将数组分为两部分,使得左半部分 ≤ pivot,右半部分 ≥ pivot。
- 基准值归位:无论哪种实现,最终
pivot
都会被放到正确的位置(左侧元素 ≤ 它,右侧元素 ≥ 它)。
性能差异
修改后的版本(
arr[j] >= pivot
)在处理大量重复元素时更高效:- 三路划分思想:通过将相等元素集中在一侧,减少后续递归中对重复元素的处理。
- 减少递归深度:重复元素越多,性能优势越明显。
示例验证
对于数组
[6, 3, 8, 2, 9, 1]
,两种实现的排序结果相同,但分区过程可能不同:- 原代码:分区后可能为
[1, 3, 2, 6, 9, 8]
(基准值6
左侧有部分较小元素)。 - 修改后:分区后可能为
[3, 2, 1, 6, 9, 8]
(基准值6
左侧集中了更多 ≤6 的元素)。
总结
特性 原代码 ( arr[j] > pivot
)修改后 ( arr[j] >= pivot
)正确性 ✅ 正确 重复元素处理 分散到两侧 集中到左侧 性能(大量重复元素) 一般 更优(减少递归) 基准值位置 可能偏向右侧 可能偏向左侧 建议
如果数据中重复元素较多,推荐使用
arr[j] >= pivot
,因为它更符合三路划分快速排序的思想(将数组分为<pivot
、=pivot
、>pivot
三部分),能有效减少递归次数。对于随机数据,两种实现性能差异不大。 -
-
2025-6-9 23:02:04@
C++ 快速排序教程
一、什么是快速排序?
快速排序(Quick Sort)是一种高效的排序算法,它基于**分治法(Divide and Conquer)**的思想:
- 基本思想:
- 从数组中选出一个“基准”元素(pivot)
- 将所有比基准小的元素放到它的左边
- 所有比基准大的元素放到它的右边
- 然后对左右两个子数组递归地进行同样的操作
这个过程称为分区(partition)。
二、快速排序的优点
- 平均时间复杂度为 O(n log n)
- 原地排序,空间复杂度为 O(log n)(因为递归调用栈)
三、通俗易懂的图解思路
假设我们要排序数组:
[6, 3, 8, 2, 9, 1]
- 选一个基准数(比如选第一个数
6
) - 把小于
6
的放左边,大于6
的放右边 →[3, 2, 1, 6, 9, 8]
- 对左右两部分继续递归执行上述操作
四、C++ 实现代码(带注释)
#include <iostream> using namespace std; // 分区函数:将数组分成两部分 int partition(int arr[], int left, int right) { int pivot = arr[left]; // 选取最左边的元素作为基准 int i = left + 1; // 左指针,找比 pivot 大的值 int j = right; // 右指针,找比 pivot 小的值 while (true) { // 向右移动 i,直到找到比 pivot 大的数 while (i <= j && arr[i] < pivot) i++; // 向左移动 j,直到找到比 pivot 小的数 while (i <= j && arr[j] > pivot) j--; // 如果 i 和 j 还没交叉,交换它们指向的值 if (i <= j) { swap(arr[i], arr[j]); i++; j--; } else { break; } } // 最后把 pivot 放到中间正确的位置 swap(arr[left], arr[j]); return j; // 返回 pivot 的位置 } // 快速排序主函数(递归) void quickSort(int arr[], int left, int right) { if (left >= right) return; // 递归终止条件 // 分区操作,得到基准的位置 int pivotIndex = partition(arr, left, right); // 递归排序左半部分 quickSort(arr, left, pivotIndex - 1); // 递归排序右半部分 quickSort(arr, pivotIndex + 1, right); } // 主函数测试 int main() { int arr[] = {6, 3, 8, 2, 9, 1}; int n = sizeof(arr) / sizeof(arr[0]); cout << "排序前:" << endl; for (int i = 0; i < n; ++i) { cout << arr[i] << " "; } cout << endl; quickSort(arr, 0, n - 1); // 调用快速排序 cout << "排序后:" << endl; for (int i = 0; i < n; ++i) { cout << arr[i] << " "; } cout << endl; return 0; }
五、代码解释
函数说明:
-
partition()
:- 功能:选择基准,把小的放左边,大的放右边
- 返回值:基准最终所在的位置
-
quickSort()
:- 功能:递归地对左右两边进行排序
关键点:
- 使用双指针
i
和j
来扫描数组 - 每次交换不符合条件的元素
- 最后把基准放到正确位置
六、示例输出
排序前: 6 3 8 2 9 1 排序后: 1 2 3 6 8 9
七、常见问题解答
Q1: 快速排序是稳定排序吗?
不是。快速排序在交换过程中可能会打乱相同元素的相对顺序。
Q2: 如何优化快速排序?
- 随机选择基准(避免极端情况)
- 三数取中法(mid of three)
- 对小数组使用插入排序
八、总结
特性 描述 时间复杂度 平均 O(n log n),最坏 O(n²) 空间复杂度 O(log n)(递归栈) 是否稳定 否 是否原地排序 是
如果你理解了“分区”的概念,快速排序就变得非常简单啦!希望这篇教程能帮你彻底掌握它 😊
- 基本思想:
-
2025-6-9 22:59:44@
C++ 快速排序教程
一、快速排序简介
快速排序(Quick Sort)是一种高效的排序算法,采用分治策略(Divide and Conquer)。它通过一个称为“基准”(pivot)的元素将数组分成两个子数组:
- 一部分比基准小
- 一部分比基准大
然后递归地对这两部分进行快速排序,最终实现整个数组的有序。
特点:
- 平均时间复杂度:O(n log n)
- 最坏情况:O(n²)(当数组已基本有序或所有元素都相等时)
- 原地排序(不需要额外空间)
- 不稳定排序
二、快速排序的基本思想
- 选择基准值(pivot):从数组中选一个元素作为基准。
- 分区(Partition):把数组划分为两部分,使得左边元素 ≤ pivot,右边元素 ≥ pivot。
- 递归处理左右两部分:对左半部分和右半部分分别进行快速排序。
三、快速排序步骤详解
我们以数组
[6, 3, 8, 2, 9, 1]
为例:- 选基准:通常选最后一个元素
1
作为 pivot。 - 分区操作:
- 遍历数组,将小于等于 pivot 的数放到左边,大于 pivot 的数放到右边。
- 最终 pivot 放到正确位置。
- 递归排序左右子数组。
四、C++ 实现代码(带详细注释)
#include <iostream> using namespace std; // 打印数组函数 void printArray(int arr[], int size) { for (int i = 0; i < size; ++i) cout << arr[i] << " "; cout << endl; } // 分区函数:将数组分为两部分,并返回基准的位置 int partition(int arr[], int left, int right) { int pivot = arr[right]; // 选取最右边的元素作为基准 int i = left - 1; // i 是小于等于 pivot 的边界指针 for (int j = left; j < right; ++j) { if (arr[j] <= pivot) { // 如果当前元素小于等于 pivot ++i; // 边界指针右移 swap(arr[i], arr[j]); // 将该元素放到左边去 } } // 最后把 pivot 放到正确位置(即中间) swap(arr[i + 1], arr[right]); return i + 1; // 返回 pivot 的位置 } // 快速排序主函数(递归) void quickSort(int arr[], int left, int right) { if (left < right) { // 分区操作,获取基准的位置 int pi = partition(arr, left, right); // 对左边子数组排序 quickSort(arr, left, pi - 1); // 对右边子数组排序 quickSort(arr, pi + 1, right); } } // 主函数测试 int main() { int arr[] = {6, 3, 8, 2, 9, 1}; int size = sizeof(arr) / sizeof(arr[0]); cout << "原始数组:" << endl; printArray(arr, size); quickSort(arr, 0, size - 1); // 调用快速排序函数 cout << "排序后数组:" << endl; printArray(arr, size); return 0; }
五、代码说明
函数名 功能 partition()
将数组分为两部分,并返回 pivot 的位置 quickSort()
递归调用自身,对左右子数组进行排序 main()
测试代码,输入数组并输出排序结果
六、示例运行结果
原始数组: 6 3 8 2 9 1 排序后数组: 1 2 3 6 8 9
七、优化建议
- 随机选择 pivot:避免最坏情况(如数组已经有序)。
- 三数取中法:选择首、中、尾三个元素的中间值作为 pivot。
- 小数组切换插入排序:对于长度较小的子数组(如 < 10),使用插入排序效率更高。
八、总结
快速排序是面试与实际开发中最常用的排序算法之一。掌握它的原理和实现方式,有助于你更好地理解分治思想以及递归编程技巧。
如果你能自己默写一遍快排代码并解释清楚每一步的作用,那你就真正掌握了这个算法!
如有需要,我还可以提供:
- 随机 pivot 的版本
- 非递归实现
- 时间性能测试对比
是否需要这些内容?
- 1