快速排序学习

由于之前做有一题看到题解用了快排提升效率，就浅学了一下快速排序，还是似懂非懂。
首先快排的核心有两点，哨兵划分和递归。

• 哨兵划分：以数组中的某个数（一般为首位）为基准数，将数组划分为两个部分，小于基准数的都在左部分，大于基准数的都在右部分。（也就是说此时基准数的位置已经正确了）
• 递归：除了基准数已经处于正确位置，其他两部分还需要继续递归执行哨兵划分，当划分到子数组长度都为 1 了，那就没什么好划分的了，说明此时数组已经排序完了。
• 示例代码如下：

•   // 递归部分// l，r：子数组左右边界public void quickSort(int[] nums, int l, int r){// 说明数组长度被划分到此时为 1 了if(l>=r)return;// i 为基准数坐标，此时 i 左部分都小于 nums[i]，右部分大于 nums[i]int i=partition(nums, l, r);// 对左右两部分递归执行哨兵划分quickSort(nums,l,i-1);quickSort(nums,i+1,r);}// 哨兵划分int partition(int[] nums, int l, int r) {int i=l, j=r;while(i<j){// 先从右边往前找比基准数小的，这个 i<j 的作用是：// 首先不会数组越界，其次它保证了不会出现错误的交换// 因为 i 左边的都是划分完的，j 右边的也都是划分完的，不应该再变动while(i < j && nums[j] >= nums[l]) j--;// 再从左边往后找比基准数大的while(i < j && nums[i] <= nums[l]) i++;// 然后把小的换到左边，大的换到右边swap(nums, i, j);}// 因为此时大致为//  l    i  j// 中 小 小 大 大// 所以最后还需要把基准数移到正确的位置swap(nums, i, l);return i;}// 交换 nums[i] 和 nums[j]void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
  

• 时间复杂度的话不难看出，哨兵划分操作是 O(N)，递归是递归 logN 轮，所以时间复杂度 O(logN) ,所以总共是 O(N logN)
• 最差情况下，每次哨兵划分都划分出 N-1 长度的数组以及长度 1 的数组，那时间复杂度就为 O(N²) 了
• 空间复杂度的话递归深度最好的情况平均情况下都是 logN，数组完全倒序让你排成正序那深度就为 N 了

算法优化

快排常见优化手段有「Tail Call」和「随机基准数」两种

Tail Call

上面也说了，因为是选取最左边的数为基准数，所以如果数组完全倒序，那么递归深度就会达到 N，也就是说最差空间复杂度为 O(N)

• 每轮递归时，仅对 较短的子数组 执行哨兵划分 partition() ，就可将最差的递归深度控制在 O(logN) （每轮递归的子数组长度都 ≤ 当前数组长度 / 2），即实现最差空间复杂度 O(logN) ，那么只需要修改 quickSort 部分即可

•   void quickSort(int[] nums, int l, int r) {// 子数组长度为 1 时终止递归while (l < r) {// 哨兵划分操作int i = partition(nums, l, r);// 仅递归至较短子数组，控制递归深度if (i - l < r - i) {quickSort(nums, l, i - 1);l = i + 1;} else {quickSort(nums, i + 1, r);r = i - 1;}}}
  

随机基准数：

由于每次都是取数组首位为基准数，所以当数组完全有序或完全倒序时，partition() 每次都是只划分了一个元素。也就是说当前情况下选择首位为基准数是最差的选择，但是我们仍然每次都坚定选择了最差的选择。
那么使用随机函数 ，每轮在子数组中随机选择一个元素作为基准数，就可以极大概率避免以上劣化情况。
值得注意的是，由于仍然可能出现最差情况（运气真的差到极点，每次都随机到首位，跟不随机一样），因此快速排序的最差时间复杂度仍为 O(N²) 。

代码仅需修改 partition() 方法，其余方法不变，在此省略。这个就很好理解了

•   int partition(int[] nums, int l, int r) {// 在闭区间 [l, r] 随机选取任意索引，并与 nums[l] 交换int ra = (int)(l + Math.random() * (r - l + 1));swap(nums, l, ra);// 以 nums[l] 作为基准数int i = l, j = r;while (i < j) {while (i < j && nums[j] >= nums[l]) j--;while (i < j && nums[i] <= nums[l]) i++;swap(nums, i, j);}swap(nums, i, l);return i;}
  

• 参考原文