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

题目描述
快速排序是一种高效的排序算法，平均时间复杂度为O(n log n)。其核心思想是分治法：选择一个基准元素，将数组划分为左右两部分，使得左边所有元素小于等于基准，右边所有元素大于等于基准，然后递归排序左右子数组。划分方法的不同会影响算法性能和稳定性。本题要求手写快速排序，并对比三种常见的划分方法：Lomuto划分、Hoare划分和双指针划分。

解题过程

1. 算法框架
   快速排序的递归框架如下：

   def quick_sort(arr, low, high):
       if low < high:
           # 选择划分方法，获取基准位置
           pivot_index = partition(arr, low, high)
           # 递归排序左半部分
           quick_sort(arr, low, pivot_index - 1)
           # 递归排序右半部分
           quick_sort(arr, pivot_index + 1, high)
   

   关键在于partition函数的实现。

2. Lomuto划分

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

     def partition_lomuto(arr, low, high):
         pivot = arr[high]
         i = low - 1
         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
     

   • 特点：
     • 实现简单，但效率较低。
     • 当数组已排序时，退化为O(n²)。
     • 不稳定（交换可能改变相等元素的顺序）。

3. Hoare划分

   • 步骤：
     1. 选择第一个元素arr[low]作为基准。
     2. 初始化指针i = low - 1，j = high + 1。
     3. 循环执行：
        • 从右向左移动j，直到arr[j] <= pivot。
        • 从左向右移动i，直到arr[i] >= pivot。
        • 若i < j，交换arr[i]和arr[j]；否则返回j。
   • 代码实现：

     def partition_hoare(arr, low, high):
         pivot = arr[low]
         i, j = low - 1, high + 1
         while True:
             j -= 1
             while arr[j] > pivot:
                 j -= 1
             i += 1
             while arr[i] < pivot:
                 i += 1
             if i < j:
                 arr[i], arr[j] = arr[j], arr[i]
             else:
                 return j
     

   • 递归调用调整：
     需将递归改为quick_sort(arr, low, j)和quick_sort(arr, j+1, high)。
   • 特点：
     • 交换次数少，效率高于Lomuto。
     • 不稳定。

4. 双指针划分（三数取中优化）

   • 步骤：
     1. 使用"三数取中法"选择基准：取arr[low]、arr[mid]、arr[high]的中位数，交换到arr[low]位置。
     2. 初始化pivot = arr[low]，指针i = low，j = high。
     3. 循环执行：
        • 从右向左移动j，直到arr[j] <= pivot。
        • 从左向右移动i，直到arr[i] >= pivot。
        • 若i < j，交换arr[i]和arr[j]；否则交换pivot和arr[j]，返回j。
   • 代码实现：

     def median_of_three(arr, low, high):
         mid = (low + high) // 2
         if arr[low] > arr[mid]:
             arr[low], arr[mid] = arr[mid], arr[low]
         if arr[low] > arr[high]:
             arr[low], arr[high] = arr[high], arr[low]
         if arr[mid] > arr[high]:
             arr[mid], arr[high] = arr[high], arr[mid]
         arr[low], arr[mid] = arr[mid], arr[low]  # 中位数放到low位置
     
     def partition_dual(arr, low, high):
         median_of_three(arr, low, high)
         pivot = arr[low]
         i, j = low, high
         while i < j:
             while i < j and arr[j] >= pivot:
                 j -= 1
             while i < j and arr[i] <= pivot:
                 i += 1
             if i < j:
                 arr[i], arr[j] = arr[j], arr[i]
         arr[low], arr[j] = arr[j], arr[low]
         return j
     

   • 特点：
     • 避免最坏情况，性能稳定。
     • 不稳定。

5. 三种方法对比

   划分方法	平均时间复杂度	最坏情况	稳定性	优化空间
   Lomuto	O(n log n)	O(n²)	不稳定	简单但慢
   Hoare	O(n log n)	O(n²)	不稳定	交换次数少
   双指针+三数取中	O(n log n)	O(n log n)	不稳定	抗退化能力强

总结
实际应用中推荐双指针划分结合三数取中法，有效避免已排序数组导致的性能退化。若需稳定性，可改用归并排序。