⚡第二课《快速排序大冒险》⚡—— 糖果王国的队长分队魔法 故事开始糖果王国大比赛在算法大陆上除了“归并魔法”之外还有一种速度特别快的魔法⚡快速排序Quick Sort⚡这一天糖果王国举行了一场“糖果排队大赛”国王拿出了一排糖果数字5 2 8 1 7要求从小到大站队同学们准备也像上节课一样慢慢拆。但这时汉克老师出现了他说⚡“今天我们换个新方法”⚡“先给数字选个基准数字再去快速排排看” 一、什么是快速排序快速排序最核心的思想1、 选一个“基准数字”也叫pivot基准数1例如2 8 5 1 72选5当队长3然后 比5小的站左边2 1 比5大的站右边8 74于是变成2 1 5 8 75神奇的事情来了 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是谁右边侦察兵。往左走。 五、选择队长pivotint 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 42、⚠️ 注意这里5并不是“真正固定不动的队长”3、在这个快排程序里pivot a[(lr)/2]pivot只是 “参考值”不是“必须站在原地的人”4、 很多同学误以为pivot一定要亲自交换其实❌ 不是5、 pivot真正作用只是“告诉大家小的去左边大的去右边” 二开始完整模拟1、数组1 2 5 3 42、 位置编号下标: 0 1 2 3 4 数字: 1 2 5 3 43、 pivot是谁程序pivot a[(lr)/2]这里l 0 r 4所以mid (04)/2 2因此pivot a[2] 5 三、侦察兵出发1、左侦察兵 ii 02、右侦察兵 jj 43、现在i j ↓ ↓ 1 2 5 3 4四、i开始找小于pivot的数字1、代码while(a[i] pivot) { i; }2、pivot53、第一次a[i] 1判断1 5成立。i右移i 14、第二次a[i] 2判断2 5成立。i继续右移i 25、第三次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 45、 交换后1 2 4 3 56、 大家都震惊了很多同学在这里突然明白了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基准数✅ 什么是双指针✅ 如何交换数字✅ 如何递归排序 下节课预告下一课⚔️《分治算法挑战赛》⚔️我们会学习 更多分治魔法