【视频讲解脚本】 主题：快速排序（Quick Sort）——从原理到高效实现 时长：≈ 6 分钟 风格：动画 + 板书 + 关键代码高亮 语言：中文（配中英双语字幕） --- ### 片头（0:00 – 0:05） 【动画】LOGO 旋转出现 【旁白】 “欢迎来到算法实验室！今天，我们一起拆解快速排序。” --- ### 1. 引入（0:05 – 0:25） 【动画】一张杂乱无序的柱状图，数字随机跳动 【旁白】 “面对这样一堆无序数字，我们怎样让电脑在几毫秒之内排好顺序？答案就是——快速排序。” --- ### 2. 核心思想（0:25 – 0:45） 【板书】“分治（Divide & Conquer）” 【动画】把长条切成左右两段，再递归地切 【旁白】 “快速排序的核心是‘分而治之’： 1. 选一个‘分界点’； 2. 把数据切成‘小’和‘大’两块； 3. 对两块再分别排序。” --- ### 3. 三步走流程（0:45 – 1:20） 【动画】三个步骤依次出现 1️⃣ 选分界点 x 2️⃣ 调整区间（Partition） 3️⃣ 递归处理 【旁白】 “步骤看似简单，但魔鬼在细节。我们先看最直观的写法。” --- ### 4. 直观实现（1:20 – 2:30） 【代码高亮】 ``` vector a, b; for (int i = l; i <= r; i++) if (q[i] <= x) a.push_back(q[i]); else b.push_back(q[i]); q.clear(); for (int v : a) q.push_back(v); for (int v : b) q.push_back(v); ``` 【动画】 - 创建两个空桶 a、b - 数字逐个跳进对应桶 - 桶倒回数组 【旁白】 “思路清晰，但缺点也明显：额外开两个数组，内存翻倍。” --- ### 5. 高效原地分区（2:30 – 4:00） 【板书】“双指针原地分区” 【动画】 - 左指针 i（黄色）从 left 出发 - 右指针 j（蓝色）从 right 出发 - 中间出现分界点 x（红色标记） 【动画分镜】 1. i 向右扫，遇到 ≥x 停 2. j 向左扫，遇到 ≤x 停 3. 交换 i、j 的值 4. 重复直到 i ≥ j 【旁白】 “全程不开新数组，只用两个指针和一次交换，空间复杂度 O(1)。” --- ### 6. 完整代码（4:00 – 5:00） 【分屏】左侧动画，右侧代码 ```cpp void quick_sort(int q[], int l, int r) { if (l >= r) return; int x = q[(l + r) >> 1]; // 1. 分界点 int i = l - 1, j = r + 1; // 2. 指针初始化 while (i < j) { do i++; while (q[i] < x); do j--; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j); // 3. 递归 quick_sort(q, j + 1, r); } ``` 【旁白】 “注意两个细节： - 指针先自增/自减再判断，避免越界； - 递归边界用 j 和 j+1，确保不重复。” --- ### 7. 复杂度分析（5:00 – 5:30） 【动画】最好 O(n log n) vs 最坏 O(n²) 【旁白】 “平均时间复杂度 O(n log n)，空间 O(log n)。 最坏情况发生在数组已排序且 x 选端点，随机选 x 可把概率降到极低。” --- ### 8. 小结 & 拓展（5:30 – 6:00） 【板书回顾】 - 选点 - 分区 - 递归 【旁白】 “快速排序是所有 O(n log n) 算法里常数最小的，因此被称为‘最快的排序’。 下一期，我们将对比它与归并排序的异同，敬请期待！” --- ### 片尾（6:00） 【动画】一键三连动态图标 【字幕】“点赞、关注、转发，算法不迷路！”