题目描述

原题链接：https://leetcode-cn.com/problems/sort-an-array/

解题思路

7. 手撕快速排序 - 图1
7.24 感悟：

33和34行代码，在内 while 循环中使用 i < j 作为前提判断条件肯定要比 i != h 及 j != l 要好记得多，但是要统一成 i < j 的代价就是：哨兵 j 必须先于哨兵 i 先走。原因如下：
假设数组只有 3 个数为：1，2，3 并且已经有序。假设用 i < j 作为前提判断条件，并且让哨兵 i 先走的话，哨兵 i 会在索引为 1 的地方停下来，即数字 2 的位置；然后哨兵 j 出发：首先 3 小于切分元素 1，哨兵 j 向左走一步到了 2 这个位置，此时 2 仍然比 1 大，此时哨兵 j 应该继续往左走的，但注意这个时候 i = 1 和 j = 1 是相等的，而又因为我们内循环的前提判断条件是 i < j，所以哨兵 j 不会继续往左走，而是直接跳出循环。跳出循环后，由于索引 j 和切分元素索引不同，故交换位置，最后数组变为：2，1，3！可以看到，本来数组就是有序的，这么一整就变成无序的了！

所以，总结：要想让我们更容易书写快速排序，也就是下面 33、34、35、36 行代码的前提判断条件都写成 i < j 这样一样的代码的话，就必须让哨兵 j 先走，然后再走哨兵 i ！因为我们的切分元素置于最左侧，所以要先让哨兵 j 从右往左不受哨兵 i 的提前限制而出发（同样的，如果你的切分元素在最右边，那你完全可以让 i 先走）！假设最好的情况是数组有序：

倘若让哨兵 j 先走：那哨兵 j 会一直探测到切分元素处而停止，此时由于 i = j 不满足 i < j 所以哨兵 i 也就不会出发了。此时切分元素与哨兵 j 所在元素相等，也就不会交换位置，数组仍然有序。

但倘若让哨兵 i 先从左向右走，由于哨兵 i 不管怎样都会越过切分元素（就算数组是有序的也会越过切分元素），导致哨兵 j 由于 i < j 的限制而永远无法到达切分元素处，从而使切分元素与哨兵 j 所在元素由于索引不同而交换位置，最后让本就有序的数组变成无序的。

// 2021/7/24 改进后版本
class Solution {
public int[] sortArray(int[] nums) {
   quickSort(nums, 0, nums.length - 1);
   return nums;
}
public void quickSort(int[] nums, int l, int h) {
   if(l >= h) return; // 切到只剩一个数就不用再切了！已经全部快排完毕了！
   int m = partition(nums, l, h); // 依据切分获得切开左右俩区间的索引;同时将切分元素排好序
   quickSort(nums, l, m - 1);
   quickSort(nums, m + 1, h);
}
// 切分两个作用:
// 1. 获取切开原数组左右俩区间的索引 j ，在第40行代码体现
// 2. 将切分元素在原数组中排好序，第39行代码体现
public int partition(int[] nums, int l, int h) {
   // 取最左边的元素为切分元素，本身是没毛病的；
   // 但是当数据全为逆序时，其排序的时间复杂读和冒泡排序差不多；
   // 所以我们改进一下，随机化元素来当切分元素。
   // int cut = nums[l]; 
   // 切分的原理还是以最左边的元素为切分元素；
   // 只是先把原先的最左边的元素和随机元素交换位置；
   // 使随机元素成为最左边元素
   // 这样选择的切分元素在逆序数组的情况下时间复杂度就不会太大了！
   swap(nums, l, new Random().nextInt(h - l + 1) + l); // 随机化，防止最坏情况
   int cut = nums[l];
   int i = l, j = h;
   while(i < j) {
       while(i < j && nums[j] >= cut) j--; // 切分元素在最左侧，并且用 i < j 做判断条件，故让 j 先走
       while(i < j && nums[i] <= cut) i++;
       if(i < j) swap(nums, i, j); // i < j 才交换，否则跳出来
   }
   // 将切分元素 nums[l] 换到属于它的位置，并返回其索引 j 
   swap(nums, l, j);
   return j;
}
public void swap(int[] nums, int i, int j) {
   int tmp = nums[i];
   nums[i] = nums[j];
   nums[j] = tmp;
}
}

// 《算法4》版本
class Solution {
public int[] sortArray(int[] nums) {
   quickSort(nums, 0, nums.length - 1);
   return nums;
}
public void quickSort(int[] nums, int l, int h) {
   if(l >= h) return; // 切到只剩一个数就不用再切了！已经全部快排完毕了！
   int mid = partition(nums, l, h); // 依据切分获得切开左右俩区间的中间索引
   quickSort(nums, l, mid - 1);
   quickSort(nums, mid + 1, h);
}
// 切分获取切开原数组左右俩区间的中间索引
// 同时确定切分元素在原数组中的位置
public int partition(int[] nums, int l, int h) {
   // 取最左边的元素为切分元素，本身是没毛病的；
   // 但是当数据全为逆序时，其排序的时间复杂读和冒泡排序差不多；
   // 所以我们改进一下，选用中间的元素来当切分元素。
   // int cut = nums[l]; 
   // 切分的原理还是以最左边的元素为切分元素；
   // 只是把中间的元素换和最左边的元素交换位置；
   // 这样选择的切分元素在逆序数组的情况下时间复杂度就不会太大了！
   swap(nums, l, (l + h) / 2);
   int cut = nums[l];
   int i = l, j = h + 1;
   while(i < j) {
       while(i != h && nums[++i] < cut);
       while(j != l && nums[--j] > cut);
       if(i >= j) break; // 如果俩指针相遇，说明没有再交换的必要的，可以确定切分元素的位置了。
       swap(nums, i, j);
   }
   // 将切分元素 nums[l] 换到属于它的位置，并返回其索引 j 
   swap(nums, l, j);
   return j;
}
public void swap(int[] nums, int i, int j) {
   int tmp = nums[i];
   nums[i] = nums[j];
   nums[j] = tmp;
}
}