排序之快速排序

代码

class Solution {
    public int[] sortArray(int[] nums) {
        merge(nums, 0, nums.length - 1);
        return nums;
    }
    private void merge(int[] nums, int l, int r){
        if(l >= r) return;
        // 随机选取主元
        int i = new Random().nextInt(r - l + 1) + l;
        int temp = nums[i];
        nums[i] = nums[l];
        nums[l] = temp;
        int idx = sort(nums, l, r);
        merge(nums, l, idx - 1);
        merge(nums, idx + 1, r);
    }
    private int sort(int[] nums, int l, int r){
        int tmp = nums[l];
        int i = l;
        int j = r;
        while(i != j){
            while(nums[j] >= tmp && i < j){
                j--;
            }
            while(nums[i] <= tmp && i < j){
                i++;
            }
            if(i < j){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        nums[l] = nums[i];
        nums[i] = tmp;
        return i;
    }
}

过程

        先给出一个待排序的数组
请添加图片描述
        上述代码有两个主要方法，merge和sort方法，首先进入的是merge方法，进入merge方法，if条件，l为0，r为nums.length-1，不满足条件，暂时不用看随机主元选取的下面四行代码，之后进入了sort方法，l为0，r为nums.length - 1。sort方法，首先将首个元素4的值赋值给了tmp，i为首元素下标，j为末尾元素下标。进入i!=j，进入while循环，内层第一个while循环查找比tmp小的元素对应的下标，第二个while循环查找比tmp大的元素的下标，显然，经过第一个while后，j指向元素5的下标，i指向元素3的下标，之后进入if判断，i<j，满足条件，交换下标i和下标j的元素，得到如下图所示结果。
请添加图片描述
        第一次最外层while循环结束，此时，i指向3元素所在下标，j指向5元素所在下标，i!=j，继续。内层第一个while循环继续从5开始找比tmp(4)小的元素，j走到元素为1的下标位置，然后内层第二个while循环继续从3开始找比tmp(4)小的元素，走到下标1时，就停止了，原因在于while循环的第二个条件是i<j，此时i=j。走到if判断，i < j，显然i=j不满足条件。第二次外层循环结束，i=j，跳出最外层循环。此时，i和j都指向了元素1的下标。将nums[l]=nums[i]，将元素为4修改为1，nums[i]=tmp，将元素为1修改为4。
        需要注意的是，内层两个循环不能调换顺序，如果调换顺序，就如上图所示，先从3开始找比tmp(4)大的元素，i会停在7的位置，之后从5开始找比tmp小的元素，但是由于要满足i<j，j也会停在7的位置，这就会导致跳出循环后，将元素4和元素7的位置进行调换，sort方法无法使得左侧序列都小于tmp，右侧序列都大于tmp。
请添加图片描述
        sort方法结束，返回元素4所在的下标，经过一次sort方法，得到了左侧小于4的序列，和右侧大于4的序列。sort方法的作用就是将数组首元素放到排序后数组的正确位置。之后分别递归左右两侧，即[1,2,3]和[7,6,5]继续使用sort方法，看右侧，将7排序到正确位置，并返回对应下标，显然[7, 6, 5]整个序列进入sort方法后，内层第一个while循环找比7小的元素，j指向了末尾元素5的位置，第二个while循环，找比7大的元素，i最终会走到元素5的下标，if条件也不会满足。将nums[l] = nums[i],nums[i]=tmp，得到序列[5, 6, 7]，返回元素7下标，递归7左侧[5,6]，和右侧[]，显然右侧递归进入下一个merge方法因为l>r(l为5的下标，r为7的下标，递归返回7的下标，就是r，进入mergel和r分别传入7的下标+1，7的下标，l肯定大于r)而递归停止。左侧[5,6]，进入sort方法，第一个while循环，j从6开始找比5小的元素，j就走到元素5所在的下标，第二个while循环，i<j不满足这个条件，也不满足if条件，i还是指向元素5，最后nums[l]=num[i]，nums[i]=tmp，l和i下标其实是一样的，都指向了5。sort方法结束，返回5所在下标，5左侧[]，右侧[6]，继续递归merge方法，左侧因为l>r(l为5的下标，r为6的下标，返回5的下标，进入mergel和r分别传入5的下标，和5的下标-1，l肯定大于r)，右侧因为l==r(l为5的下标，r为6的下标，返回5的下标，进入mergel和r分别传入5的下标+1，和6的下标，l等于r)，而导致递归停止。
        在merge方法中，进入sort方法之前，有一个随机主元操作，如果没有该四行代码，sort默认将数组首元素作为主元，将数组排序成左侧小于数组首元素，右侧大于数组首元素。上述四行代码则是随机从数组中选取一个元素作为主元，而不是一直都是默认数组首元素。