网站免费优化_室内设计好不好学_常用的网络推广方法_网络营销策略是什么

class Solution {public int[] sortArray(int[] nums) {quickSort(nums,0,nums.length-1);return nums;}public void quickSort(int[] nums, int left, int right) {if (left >= right) {return;}int pivot = partition(nums, left, right);quickSort(nums, left, pivot - 1);quickSort(nums, pivot + 1, right);}public int partition(int[] nums, int left, int right) {// 选取三个候选元素的中位数int med = medianThree(nums, left, (left + right) / 2, right);// 将中位数交换至数组最左端swap(nums, left, med);int i = left;int j = right;while (i < j) {//先进行j--,让j先找到小的，否则让i先走，i==j时，会导致i找到大，然后与i下标进行交换，就导致大的换到了左边while (i < j && nums[j] >= nums[left]) {j--;}while (i < j && nums[i] <= nums[left]) {i++;}swap(nums, i, j);}swap(nums, left, i);return i;}int medianThree(int[] nums, int left, int mid, int right) {int l = nums[left], m = nums[mid], r = nums[right];if ((l <= m && m <= r) || (r <= m && m <= l))return mid; // m 在 l 和 r 之间if ((m <= l && l <= r) || (r <= l && l <= m))return left; // l 在 m 和 r 之间return right;}public void swap(int[] nums, int left, int right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;}
}

候选优化，对数组中的左中右取第二大的，并将它作为候选元素，减少极端情况导致出现O(n^2)：

所需排序数组为倒叙，此时如果还用最左边做基准都会出现与冒泡排序相似的快速排序

         // 选取三个候选元素的中位数int med = medianThree(nums, left, (left + right) / 2, right);// 将中位数交换至数组最左端

易错点:

1.在哨兵分划中，应该先去寻找右边小于基准的数

正确的代码：

        while (i < j) {//先进行j--,让j先找到小的，否则让i先走，i==j时，会导致i找到大，然后与i下标进行交换，就导致大的换到了左边while (i < j && nums[j] >= nums[left]) {j--;}while (i < j && nums[i] <= nums[left]) {i++;}swap(nums, i, j);}

错误的：

        while (i < j) {while (i < j && nums[i] <= nums[left]) {i++;}while (i < j && nums[j] >= nums[left]) {j--;}swap(nums, i, j);}

如果让左边先去寻找大于基准的数，那么当左边停下，左边全是小于等于基准的数

此时在让右边去寻找小于基准的数，由于i<j，那么当i==j时就停下来

在最后进行交换时，会出现基准的左边大于基准的情况

例如：

3 1 2 1 4 5 6

             i

             j

如果左边先寻找，i会在4停下，然后右边再走，也会走到4，因为i<j的条件不符合，无法进行循环了

此时在最后进行交换时，会出现基准的左边大于基准的情况

4 1 2 1 3 5 6

但是如果让右边先去寻找比基准小的数，就不会出现这样的情况

2.在哨兵分划中，边界处理

        while (i < j) {while (i < j && nums[i] <= nums[left]) {i++;}while (i < j && nums[j] >= nums[left]) {j--;}swap(nums, i, j);}

nums[i] <= nums[left]和nums[j] >= nums[left] 一定需要加上=吗？

是一定要加上的（至少这个版本是这样的）

因为，当左右两个指针所指的数都等于基准时，会死循环（i和j都无法移动，始终i<j）

4 1 1 1 4 2 4 5 6

当i和j分别走到两个红色标记的4时，就会进行死循环

参考：11.5   快速排序 - Hello 算法