快速排序两个版本以及优化

快速排序

快速排序其实存在有两个版本

版本1 Lomuto版本

Lomuto分区方案

1. 基准选择
   1. lomuto分区通常选择数组的最后一个元素作为基准值
2. 效率
   1. lomuto易于实现，但是比Hoare方法效率低，特别是在处理大量重复元素的数组时。

代码实现如下

package sorting;

public class QuickSortLomuto {
    void swap(int[] nums, int i , int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    //确定哨兵
    public int partition(int[] arr, int low, int high){
        int pivot = arr[high]; // 选择最后一个元素作为基准
        int i = low -1; //初始化i指针
        for (int j = low; j < high; j++){
            if (arr[j] <= pivot){
                i++; //移动i指针
                swap(arr,i,j);
            }
        }
        //将基准元素放到正确的位置上
        swap(arr,i+1,high);
        return i+1;
    }

    public void quickSort(int[] arr, int low, int high){
        if (low < high) {//检查是否有超过一个元素需要排序
            int pi =partition(arr,low,high);
            quickSort(arr,low,pi-1);
            quickSort(arr,pi+1,high);
        }
    }
}

版本2 Hoare版本

hoare分区

hoare版本是以双指针方法来执行分区，这样会比lomuto版本更少的元素转换

原理： 一般设置nums[left] 为基准，然后左指针往右走，走到大于基准的数停下，右指针往左走，走到小于基准的数停下，最后i==j时 与基准交换，然后开始继续递归

代码实现：

void swap(int[] nums, int i , int j){
     int tmp = nums[i];
     nums[i] = nums[j];
     nums[j] = tmp;
 }
 int partition(int[] nums, int left, int right){
     //以nums[left] 作为基准数
     int i = left, j = right;
     while (i < j){
         while (i < j && nums[j] >= nums[left]){
             j--; //从右向左找首个小于基准数的元素
         }
         while (i < j && nums[i] <= nums[left]){
             i++;
         }
         swap(nums,i,j);
     }
     swap(nums,i,left);
     return i;
 }
 void quickSort(int[] nums, int left, int right){
     //子数组长度为1时终止递归
     if (left >= right){
         return;
     }
     //哨兵划分
     int pivot = partition(nums,left,right);
     quickSort(nums,left,pivot-1);
     quickSort(nums,pivot+1,right);
 }

版本3 Hoare版本优化

原因 快速排序在某些输入下的时间效率可能降低。举一个极端例子，假设输入数组是完全倒序的，由于选择最左端元素为基准，那么哨兵在划分完之后，基准数被交换到最后端，导致左子数组长度为n-1 如此递归，每轮哨兵规划完成之后，右子数组的长度都为0

解决方案 优化哨兵划分中的基准数选取策略

代码如下

int medianThree(int[] nums, int left, int mid , int right){
     //此处使用异或运算来简化代码
     //异或规则为0 ^0 = 1^1 = 0, 0^1 = 1^0 =1
     /*
     这行代码的逻辑是：检查 nums[left] 与 nums[mid] 和 nums[left]
     与 nums[right] 的比较结果是否不同。如果其中一个是 true 而另一个是 false，
     即 nums[left] 落在 nums[mid] 和 nums[right] 之间，那么 nums[left] 可能是中间值。
      */
     if ((nums[left] < nums[mid]) ^ (nums[left] < nums[right])) return left;
     else if ((nums[mid] < nums[left]) ^ (nums[mid] < nums[right])) return mid;
     else return right;
     //同理  要不是mid,要不就是right 找一个中间值，防止出现极端问题
 }

哨兵实现如下

int partitionThree(int[] nums, int left, int right){
       //选取三个候选元素的中位数
       int med = medianThree(nums,left,(left+right)/2,right);
       //将中位数交换到数组的最左端
       swap(nums,left,med);
       //以 nums[left]作为基准数
       int i = left, j = right;
       while (i < j){
           while (i < j && nums[j] >= nums[left] ) j--;
           while (i < j && nums[i] <= nums[left]) i++;
           swap(nums,i,j);
           //3  1 2 5  4 8
       }
       swap(nums,i,left);
       return i;
   }

hoare版本 尾递归优化

原因 在某些输入下，快速排序可能占用的额空间较多。以完全倒序的输出数组为例子，由于每轮哨兵划分后右子数组长度为0，递归树的高度会达到n-1，此时需要占用O(n)大小的栈帧空间

为了防止栈帧空间的积累，我们可以在每轮哨兵排序后，比较两个子数组的长度，仅对较短的子数组进行递归。由于较短子数组的长度不会超过 𝑛/2 ，因此这种方法能确保递归深度不超过 log 𝑛 ，从而将最差空 间复杂度优化至 𝑂(log 𝑛) 。

代码如下

void quickSotrWei(int[] nums, int left, int right){
      if (left >= right) return; //子数组长度为1是终止递归

      while (left < right){
          //哨兵划分操作
          int pivot = partitionThree(nums,left,right);
          //对两个子数组中较短的那个执行快排
          if (pivot - left < right - pivot){
              quickSort(nums,left,pivot-1);
              left = pivot+1; // 生育为排序空间为[pivot+1,right]
          }else {
              quickSort(nums,pivot+1,right);
              right = pivot -1;
          }
      }
  }