野牛程序员讲少儿编程——快速排序（C++ 版）
?小朋友们，今天跟野牛程序员来聊聊一个超级厉害的排序算法—— 快速排序 ！它快得就像赛车一样，能在短时间内把一堆乱七八糟的数字排好序！?
? 什么是快速排序？
快速排序，简称 快排（Quicksort），是一种 “分而治之” 的排序方法。它的思路就像整理玩具一样：
选一个基准值（pivot），比如拿起一个玩具? 说：“好，大家跟它比比大小！”
比它小的放左边，比它大的放右边，这样，玩具堆就分成了两部分。
左右两边再各自继续排序，直到所有玩具都排好为止！
这个过程就像分组比赛一样，把问题一拆二，二拆四，最后轻松解决！?
? 快速排序是怎么工作的？
来看看野牛程序员举的一个例子，假设有这样一组数字：
64, 25, 12, 22, 11
要把它排成从小到大的顺序，快排会这么做：
第 1 步：选择基准值（Pivot）
野牛程序员随便选一个基准值，最常见的做法是选最后一个数作为基准值。
这里选 11 作为 pivot（基准值）：
64, 25, 12, 22, [11]
现在，所有比 11 小的放左边，比 11 大的放右边：
[11], 25, 12, 22, 64
第一个小朋友 “11” 已经站在了正确的位置 ?，它再也不会动了！
第 2 步：继续对右边的数字排序
剩下的数字 25, 12, 22, 64 还没排好，野牛程序员再挑一个基准值，这次选 最后一个数 64。
[11], 25, 12, 22, [64]
所有比 64 小的放左边，比 64 大的放右边（但是没比它大的了）
[11], 25, 12, 22, [64] ✅
哇，64 也站对了位置！ ??
第 3 步：继续对中间的数字排序
现在，剩下的 25, 12, 22 还没排好，野牛程序员再来一次！
选最后一个数 22 作为 pivot：
[11], 25, 12, [22], 64
小于 22 的放左边，大于 22 的放右边：
[11], 12, [22], 25, 64
太棒了，22 也站对了位置！ ???
第 4 步：剩下的 12 和 25 还没排序
但是，12 和 25 只剩两个数了，它们已经是正确的顺序了：
[11], [12], [22], [25], [64]
完美！所有数字都站对了队伍，排序完成！✅
? C++ 代码实现
快排的代码其实并不难！来看看 C++ 版本的实现吧：
#include <iostream>
using namespace std;
// 分区函数：把小的放左边，大的放右边
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选最后一个数作为基准值
int i = low - 1; // i 负责记录比 pivot 小的位置
for (int j = low; j < high; j++) {
if (arr[j] < pivot) { // 如果当前数比 pivot 小
i++; // i 向前走一步
swap(arr[i], arr[j]); // 交换
}
}
swap(arr[i + 1], arr[high]); // 把 pivot 放到正确位置
return i + 1; // 返回 pivot 的最终位置
}
// 递归实现快速排序
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); // 递归排序右边
}
}
// 主函数
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "原始数组: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
quickSort(arr, 0, n - 1);
cout << "排序后: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}? 为什么快排这么快？
快排利用 分而治之 的思想，每次把问题分成两半，快速缩小问题的规模。
最优情况：每次刚好平分，时间复杂度 O(n log n)，非常快！?
最坏情况：如果每次选的 pivot 都是最大或最小，快排可能会退化成 O(n²)，但优化后可以避免！
? 野牛程序员：小朋友们学到了什么？
快速排序是一种“分而治之”的排序方法
选一个基准值，把小的放左边，大的放右边
递归地对左右两部分排序
它非常快，适用于大规模数据排序！
小朋友们，快去试试 用 C++ 代码自己实现快速排序吧！ ???
