手写快速排序（含三种划分方法对比）

题目描述
要求手写实现快速排序算法，并理解不同的划分（Partition）策略对性能的影响。快速排序的核心是通过一趟划分将待排序列分为独立的两部分，其中一部分的所有元素均比另一部分的元素小，然后递归地对这两部分进行排序。

解题过程

1. 算法框架
快速排序采用分治思想，步骤如下：

1. 划分：选取基准值（pivot），将数组重新排列，所有比pivot小的元素放在其左侧，比pivot大的放在右侧。
2. 递归：对pivot左侧和右侧的子数组递归执行快速排序。
3. 合并：由于每趟划分后pivot已位于最终位置，无需合并操作。

2. 基础划分方法：Lomuto划分

• 步骤：
  1. 选择最右元素作为pivot（例如arr[high]）。
  2. 初始化指针i = low-1，用于标记小于pivot的子数组的末尾。
  3. 遍历j从low到high-1：
     • 若arr[j] <= pivot，则i++，交换arr[i]和arr[j]。
  4. 将pivot放到正确位置：交换arr[i+1]和arr[high]。
  5. 返回pivot的位置i+1。
• 代码示例：

  def lomuto_partition(arr, low, high):
      pivot = arr[high]  # 选择最右元素为pivot
      i = low - 1        # 小于pivot区域的右边界
      for j in range(low, high):
          if arr[j] <= pivot:
              i += 1
              arr[i], arr[j] = arr[j], arr[i]
      arr[i+1], arr[high] = arr[high], arr[i+1]
      return i + 1
  

• 特点：代码简洁，但当所有元素相等时仍进行交换，效率较低。

3. 优化划分方法：Hoare划分

• 步骤：
  1. 选择中间元素作为pivot（例如arr[(low+high)//2]）。
  2. 初始化双指针i = low-1, j = high+1。
  3. 循环执行：
     • i向右移动，直到找到arr[i] >= pivot。
     • j向左移动，直到找到arr[j] <= pivot。
     • 若i >= j，返回j作为划分点；否则交换arr[i]和arr[j]。
• 代码示例：

  def hoare_partition(arr, low, high):
      pivot = arr[(low + high) // 2]  # 选择中间元素
      i, j = low - 1, high + 1
      while True:
          i += 1
          while arr[i] < pivot:  # 找到左侧大于等于pivot的元素
              i += 1
          j -= 1
          while arr[j] > pivot:  # 找到右侧小于等于pivot的元素
              j -= 1
          if i >= j:
              return j
          arr[i], arr[j] = arr[j], arr[i]
  

• 特点：交换次数更少，效率更高，但需注意递归边界应划分为[low, j]和[j+1, high]。

4. 应对重复元素的优化：三路划分

• 适用场景：当数组中存在大量重复元素时，将数组划分为三部分（小于、等于、大于pivot）。
• 步骤：
  1. 初始化指针lt = low, i = low, gt = high。
  2. 选择pivot（如arr[low]），遍历i从low到gt：
     • 若arr[i] < pivot，交换arr[lt]和arr[i]，lt++，i++。
     • 若arr[i] > pivot，交换arr[gt]和arr[i]，gt--（此时i不移动）。
     • 若arr[i] == pivot，i++。
  3. 递归排序[low, lt-1]和[gt+1, high]。
• 代码示例：

  def three_way_partition(arr, low, high):
      pivot = arr[low]
      lt, i, gt = low, low, high
      while i <= gt:
          if arr[i] < pivot:
              arr[lt], arr[i] = arr[i], arr[lt]
              lt += 1
              i += 1
          elif arr[i] > pivot:
              arr[gt], arr[i] = arr[i], arr[gt]
              gt -= 1
          else:
              i += 1
      return lt, gt  # 返回等于pivot的区间边界
  

5. 完整快速排序实现（以Hoare划分为例）

def quicksort(arr, low, high):
    if low < high:
        pi = hoare_partition(arr, low, high)  # 获取划分点
        quicksort(arr, low, pi)    # 递归左半部分
        quicksort(arr, pi + 1, high)  # 递归右半部分

6. 关键点总结

• 稳定性：快速排序是不稳定排序（交换可能破坏顺序）。
• 时间复杂度：
  • 平均情况：\(O(n \log n)\)。
  • 最坏情况（已排序数组+固定pivot选择）：\(O(n^2)\)，可通过随机选择pivot避免。
• 空间复杂度：递归栈深度平均为\(O(\log n)\)，最坏\(O(n)\)。
• 划分方法选择：
  • Lomuto：易于理解，但交换次数多。
  • Hoare：交换次数少，效率更高。
  • 三路划分：适合重复元素多的场景，避免重复元素递归。