宜宾野牛程序员讲少儿编程——快速排序（C++ 版）

宜宾野牛程序员讲少儿编程——快速排序（C++ 版）

🦬小朋友们，今天跟宜宾野牛程序员来聊聊一个超级厉害的排序算法——快速排序！它快得就像赛车一样，能在短时间内把一堆乱七八糟的数字排好序！

什么是快速排序？

快速排序，简称快排（Quicksort），是一种“分而治之”的排序方法。它的思路就像整理玩具一样：

选一个基准值（pivot），比如拿起一个玩具 说：“好，大家跟它比比大小！”

比它小的放左边，比它大的放右边，这样，玩具堆就分成了两部分。

左右两边再各自继续排序，直到所有玩具都排好为止！

这个过程就像分组比赛一样，把问题一拆二，二拆四，最后轻松解决！

快速排序是怎么工作的？

来看看野牛程序员举的一个例子，假设有这样一组数字：

要把它排成从小到大的顺序，快排会这么做：

第 1 步：选择基准值（Pivot）

野牛程序员随便选一个基准值，最常见的做法是选最后一个数作为基准值。

这里选 11 作为 pivot（基准值）：

现在，所有比11小的放左边，比11大的放右边：

第一个小朋友“11” 已经站在了正确的位置，它再也不会动了！

第 2 步：继续对右边的数字排序

剩下的数字25, 12, 22, 64还没排好，野牛程序员再挑一个基准值，这次选最后一个数 64。

所有比64小的放左边，比64大的放右边（但是没比它大的了）

哇，64 也站对了位置！

第 3 步：继续对中间的数字排序

现在，剩下的 25, 12, 22 还没排好，野牛程序员再来一次！

选最后一个数 22 作为 pivot：

小于22的放左边，大于22的放右边：

太棒了，22 也站对了位置！

第 4 步：剩下的 12 和 25 还没排序

但是，12和25只剩两个数了，它们已经是正确的顺序了：

完美！所有数字都站对了队伍，排序完成！

C++ 代码实现

快排的代码其实并不难！来看看 C++ 版本的实现吧：

🧐 为什么快排这么快？

快排利用分而治之的思想，每次把问题分成两半，快速缩小问题的规模。

最优情况：每次刚好平分，时间复杂度O(n log n)，非常快！

最坏情况：如果每次选的 pivot 都是最大或最小，快排可能会退化成O(n²)，但优化后可以避免！

野牛程序员：小朋友们学到了什么？

快速排序是一种“分而治之”的排序方法

选一个基准值，把小的放左边，大的放右边

递归地对左右两部分排序

它非常快，适用于大规模数据排序！

小朋友们，快去试试用 C++ 代码自己实现快速排序吧！