GESP5级C++考试语法知识（十五、分治算法（二））

⚡第二课：《快速排序大冒险》⚡

—— 糖果王国的队长分队魔法

🏰 故事开始：糖果王国大比赛

在算法大陆上，

除了“归并魔法”之外，

还有一种速度特别快的魔法：

⚡快速排序（Quick Sort）⚡

这一天，

糖果王国举行了一场：

🍬“糖果排队大赛”🍬

国王拿出了一排糖果数字：

5 2 8 1 7

要求：

🌟从小到大站队！

同学们准备也像上节课一样：

慢慢拆。

但这时，

汉克老师出现了！

他说：

⚡“今天我们换个新方法！”⚡

🌟“先给数字选个基准数字，再去快速排排看”🌟

🍭 一、什么是快速排序？

快速排序最核心的思想：

1、🌟 选一个“基准数字”

也叫：

pivot（基准数）

（1）例如：

2 8 5 1 7

（2）选：

5

当队长！

（3）然后：

🌟 比5小的站左边

2 1

🌟 比5大的站右边

8 7

（4）于是变成：

2 1 5 8 7

（5）神奇的事情来了：

🌟 5的位置已经正确了！

（6）因为：

左边都比5小。

右边都比5大。

（7）然后：

再递归处理左右两边！

🌈 二、快速排序完整思想

🌟 第一步

选队长（pivot）

🌟 第二步

小的站左边。

大的站右边。

🌟 第三步

继续整理左右两边。

🌟 最后

整个队伍有序！

🍬 三、课堂实例一步一步演示

现在：

2 8 5 1 7

🌟 第一步：选队长

选：

5

🌟 第二步：左右寻找

左边找：

比5大的数字

右边找：

比5小的数字

现在：

2 8 5 1 7

左边发现：

8

太大了！

右边发现：

1

太小了！

🌟 交换！

变成：

2 1 5 8 7

现在：

左边都小于5。

右边都大于5。

🌟 最后队长归位

得到：

2 1 5 8 7

然后：

继续排：

左边：

2 1

右边：

8 7

最终：

1 2 5 7 8

🌟 四、快速排序完整版程序

#include <iostream> using namespace std; int a[100]; // 快速排序函数 void quick_sort(int l, int r) { // 如果区间不存在 if(l >= r) return; // 左右指针 int i = l; int j = r; // 选择中间数字作为基准数 int pivot = a[(l + r) / 2]; // 开始分队 while(i <= j) { // 找左边第一个 >= pivot 的数字 while(a[i] < pivot) { i++; } // 找右边第一个 <= pivot 的数字 while(a[j] > pivot) { j--; } // 停下的时候，如果没有交错 if(i <= j) { // 交换 int temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j--; } } // 递归排序左边 quick_sort(l, j); // 递归排序右边 quick_sort(i, r); } int main() { int n; cout << "请输入数字个数："; cin >> n; cout << "请输入数字：" << endl; for(int i = 0; i < n; i++) { cin >> a[i]; } // 调用快速排序 quick_sort(0, n - 1); cout << "排序后：" << endl; for(int i = 0; i < n; i++) { cout << a[i] << " "; } return 0; }

🌈 五、代码详细讲解（超详细）

🌟 一、数组定义

int a[100];

这是：

糖果仓库

例如：

5 2 8 1 7

都放在这里。

🌟 二、快速排序函数

void quick_sort(int l, int r)

意思：

排序：

l 到 r

这一段数字。

例如：

quick_sort(0,4);

表示：

排序：

第0~4个数字

🌟 三、结束条件（非常重要）

if(l >= r) return;

🧠 为什么？

如果：

只有1个数字

或者：

没有数字

就不用排序了。

🌟 四、左右指针

int i = l; int j = r;

🧠 i是谁？

左边侦察兵。

往右走。

🧠 j是谁？

右边侦察兵。

往左走。

🌟 五、选择队长（pivot）

int pivot = a[(l + r) / 2];

例如：

2 8 5 1 7

中间位置：

5

所以：

pivot = 5

🌟 六、最核心：while循环

while(i <= j)

意思：

只要左右侦察兵还没碰面。

就继续找坏蛋！

🌟 七、左边侦察兵工作

while(a[i] < pivot) { i++; }

什么意思？

左边一路寻找：

第一个不该在左边的人！

例如：

pivot是：

5

看到：

2

没问题。

继续。

看到：

8

大数出现！

停止。

🌟 八、右边侦察兵工作

while(a[j] > pivot) { j--; }

从右边寻找：

第一个不该在右边的人！

例如：

发现：

1

太小了。

应该去左边！

🌟 九、交换（最重要）

int temp = a[i]; a[i] = a[j]; a[j] = temp;

🌈 交换前

2 8 5 1 7

🌈 交换后

2 1 5 8 7

🌟 十、侦察兵继续前进

i++; j--;

因为：

刚刚那两个位置已经正确了。

继续检查别的地方。

🌟 十一、递归左右两边

左边继续排序

quick_sort(l, j);

右边继续排序

quick_sort(i, r);

🌟十二、🌟“快排最容易让同步们糊涂的情况！”🌟

1、比如这个例子：

1 2 5 3 4

右边没有“大的数”

左面只有“小的数”

2、所以很多同学会问：

❓“5怎么归位？”

❓“为什么没有交换5？”

❓“最后为什么还是对的？”

3、今天我们就：

🌈一步一步、慢动作、像动画片一样，

完整模拟！

你会彻底明白！

🌟 （一）先明确一件事（超级重要）

1、数组：

1 2 5 3 4

2、⚠️ 注意！

这里：

5

并不是：

“真正固定不动的队长”

3、在这个快排程序里：

pivot = a[(l+r)/2]

pivot只是：

🌟 “参考值”

不是：

“必须站在原地的人”

4、🌟 很多同学误以为：

pivot一定要亲自交换

其实：

❌ 不是！

5、🌟 pivot真正作用：

只是：

🌟“告诉大家：

小的去左边，

大的去右边！”🌟

🌈 （二）开始完整模拟（

1、数组：

1 2 5 3 4

2、🌟 位置编号

下标: 0 1 2 3 4 数字: 1 2 5 3 4

3、🌟 pivot是谁？

程序：

pivot = a[(l+r)/2]

这里：

l = 0 r = 4

所以：

mid = (0+4)/2 = 2

因此：

pivot = a[2] = 5

🌟 （三）、侦察兵出发！

1、左侦察兵 i

i = 0

2、右侦察兵 j

j = 4

3、现在：

i j ↓ ↓ 1 2 5 3 4

🌟（四）、i开始找小于pivot的数字

1、代码：

while(a[i] < pivot) { i++; }

2、pivot：

5

3、第一次

a[i] = 1

判断：

1 < 5

成立。

i右移：

i = 1

4、第二次

a[i] = 2

判断：

2 < 5

成立。

i继续右移：

i = 2

5、第三次

a[i] = 5

判断：

5 < 5

不成立！

6、🌟 i停下！

现在：

i 指向 5

🌟 （五）、j开始找大于pivot的数字

1、代码：

while(a[j] > pivot) { j--; }

2、第一次

a[j] = 4

判断：

4 > 5 ？

不成立！

3、🌟 j立刻停下！

现在：

j 指向 4

🌟 （六）、现在发生了什么？

1、i找到：

5

（不属于左边）

2、j找到：

4

（不属于右边）

3、🌟 所以交换！

代码：

swap(a[i], a[j]);

4、🌈 交换前

1 2 5 3 4

5、🌈 交换后

1 2 4 3 5

6、🌟 大家都震惊了！！！

很多同学在这里突然明白了：

7、⚡原来：

“5自己被换走了！”⚡

8、🌟 对！！！

pivot只是：

“参考值”

不是：

“固定位置”

🌟 （七）、继续前进

交换后：

i++; j--;

于是：

i = 3 j = 3

现在数组：

1 2 4 3 5

🌟 （八）、继续循环

因为：

i <= j

还成立。

🌟 i继续检查

a[i] = 3

判断：

3 < 5

成立。

于是：

i++

变成：

i = 4

🌟 j检查

a[j] = 3

判断：

3 > 5

不成立。

j不动。

现在：

i = 4 j = 3

🌟 （九）、循环结束！

因为：

i > j

🌟 此时数组：

1 2 4 3 5

观察：

左边：

1 2 4 3

全部：

<= 5

右边：

5

全部：

>= 5

🌟 分区成功！

🌳 （十）、递归继续

现在程序：

排左边

1 2 4 3

排右边

5

（不用排）

最后得到：

1 2 3 4 5

🌈 （十一）、同学们最容易误解的地方（重点）

很多同学以为：

❌ pivot必须待在中间

其实：

❌ 完全不是！

🌟 pivot只是“裁判”

它的作用：

小的去左边 大的去右边

🌟 pivot自己也可能被交换！

这非常正常！

🌟（十二） 、真正本质

1、快排不是：

❌“给pivot找位置”

2、而是：

🌟“让整个数组自动分区！”🌟

3、🌟 所以即使：

数字没有成对出现

4.、程序依然会：

✅ 自动交换
✅ 自动分区
✅ 自动完成排序

🌟 十三、快速排序为什么快？

因为：

每次都能：

🌟 把数字分成两边

问题越来越小。

所以：

⚡速度超级快！

🌟 十四、快排 vs 归并排序

🌟 十五、课后总结：

⚡“选一个队长，小的站左边，大的站右边！”⚡

这就是：

🌈快速排序的灵魂！

今天我们学会了：

✅ 什么是快速排序

✅ 什么是pivot（基准数）

✅ 什么是双指针

✅ 如何交换数字

✅ 如何递归排序

🌈 下节课预告

下一课：

⚔️《分治算法挑战赛》⚔️

我们会学习：

🌟 更多分治魔法！