快速排序的两种主要的划分方案

快速排序有两种主要的划分方案：Hoare Partition Scheme 和 Lomuto Partition Scheme。这两种方案在实现方式和性能特点上有显著区别。

Hoare Partition Scheme

特点：

• 由 Tony Hoare 在1961年发明，是快速排序的原始版本
• 使用两个指针从数组两端向中间移动
• 当两个指针相遇时停止

实现思路：

1. 选择最左边的元素作为基准值（pivot）
2. 左指针从左边开始，右指针从右边开始
3. 左指针向右移动，直到找到大于等于基准值的元素
4. 右指针向左移动，直到找到小于等于基准值的元素
5. 如果左指针仍在右指针左侧，交换这两个元素
6. 重复步骤3-5，直到两个指针相遇

Lomuto Partition Scheme

特点：

• 由 Nico Lomuto 提出，是更简单直观的实现方式
• 使用单个指针遍历数组
• 将数组分为三个部分：小于基准值、等于基准值、大于基准值

实现思路：

1. 选择最右边的元素作为基准值
2. 使用一个指针 i 来跟踪小于基准值的元素的边界
3. 遍历数组，将小于基准值的元素移到指针 i 的左侧
4. 最后将基准值放到正确位置

主要区别

方面	Hoare	Lomuto
复杂度	更复杂	更简单
指针数量	两个指针	一个指针
基准值位置	通常选择第一个元素	通常选择最后一个元素
交换次数	通常更少	通常更多
理解难度	较难理解	容易理解
实现难度	较难实现	容易实现
性能	平均情况下稍好	稍差一些

性能对比

• Hoare方案：平均交换次数更少，在大多数情况下性能略好
• Lomuto方案：实现简单，代码更清晰，但交换次数可能更多

两种方案的时间复杂度都是 O(n log n) 平均情况，O(n²) 最坏情况，但 Hoare 方案在实际应用中通常表现更好一些。