快速排序 - 实践中最快的排序算法
095快速排序：征服世界的算法
📰 5W1H 发明者故事
Who（何人）- 发明者是谁？
发明者：查尔斯·安东尼·理查德·霍尔（Charles Antony Richard Hoare，简称 Tony Hoare）
背景：霍尔（1934-），英国计算机科学家，牛津大学教授，图灵奖得主（1980年）。他21岁就读俄语，22岁服役，26岁发明快速排序。他还发明了 Hoare逻辑（用于程序正确性证明）和CSP（通信顺序进程），是形式化方法的先驱。他晚年还因对自己的错误决策"空指针"而道歉（C.A.R. Hoare: null reference is “my billion-dollar mistake”）。
当时的处境：1959年，霍尔在莫斯科国立大学留学，学习俄语和机器翻译技术。他的导师给他一个任务：为机器翻译程序实现一个对俄语词典单词排序的功能。当时他正在学习谢尔排序（Shell Sort），但发现可以做得更好。在一个晚上，他想出了快速排序的核心思想：选一个"枢轴"，把小的放左边，大的放右边，递归处理。他在回到英国后，用Autocode编程语言实现了它。
When（何时）- 什么时候发明的？
时间：1959年（霍尔在莫斯科期间构思），1960年首次发表
时代背景：
- 第一代高级语言（FORTRAN, ALGOL, COBOL）刚刚问世
- 排序是计算机应用中最耗时的操作，IBM的机器50%时间都在排序
- 谢尔排序（1959年）刚刚提出，是当时最好的排序之一
- 归并排序（冯·诺依曼，1945年）是理论上的最优，但需要额外空间
Where（何地）- 在哪里发明的？
地点：苏联莫斯科国立大学（构思），英国椭圆计算机公司（实现）
环境：1959年冷战高峰期，霍尔作为英国交换生在莫斯科学习。他晚上在宿舍里苦思冥想排序问题，没有计算机，只有纸和铅笔。他后来说：那个顿悟的夜晚，他完全用脑力"执行"了算法，验证了它的正确性。
What（何事）- 发明了什么？
算法：快速排序（Quicksort）
核心思想：分而治之（Divide and Conquer）
- 选枢轴（Pivot）：从数组中选一个元素作为基准
- 分区（Partition）：将数组重排，使所有 ≤ pivot 的元素在左，≥ pivot 的在右
- 递归：对左右两部分分别递归执行快速排序
关键突破：
- 原地排序（只需O(log n)栈空间）
- 平均 O(n log n)，实践中常数因子比归并排序小
- 高效利用缓存（局部访问模式）
Why（何因）- 为什么发明？
动机：霍尔学谢尔排序时，觉得它的间距策略复杂难懂。他想：有没有更自然、更快的方法？
问题：冒泡排序和插入排序都是O(n²)，不够快。归并排序需要O(n)额外空间。
洞察：如果能找到一个元素的"最终位置"，就可以把问题分成两个独立的子问题。
How（何果）- 如何实现？有什么影响？
历史影响：
- 被克努斯评价为"20世纪最重要的算法之一"
- C标准库
qsort()就是快速排序（或其变体） - 实践中比理论上更快的O(n log n)算法（如归并排序）更快的原因：更好的缓存局部性
- 内省排序（Introsort）：快速排序 + 堆排序的混合，是 C++ STL
std::sort的实现
📝 自然语言需求定义
需求名称：实现带优化的快速排序，包含三数取中选pivot、小数组切换插入排序、三路分区
功能需求
- 基本快速排序：Lomuto分区，递归实现
- 优化快速排序：三数取中 + 小数组(n<8)用插入排序
- 三路快速排序：处理大量重复元素（将数组分为<pivot、==pivot、>pivot三段）
验收标准
| 编号 | 测试场景 | 预期结果 | 验证方式 |
|---|---|---|---|
| 1 | 基本排序 [5,2,4,6,1,3] | [1,2,3,4,5,6] | 逐元素比较 |
| 2 | 逆序数组 | 正确排序 | is_sorted检验 |
| 3 | 已排序数组 | 不变 | 逐元素比较 |
| 4 | 含重复元素 | 正确排序 | is_sorted检验 |
| 5 | 三路快排处理全相同元素 | 正确，无无效交换 | is_sorted检验 |
| 6 | 单元素数组 | 不变 | 边界条件 |
| 7 | 1000个随机数 | 正确排序 | is_sorted检验 |
💻 C语言实现文件
对应文件:quicksort.c
编译运行:
gcc-oquicksort_test quicksort.c ./quicksort_test核心函数:
quicksort(arr, low, high)- 带优化的快速排序quicksort3(arr, low, high)- 三路快速排序
