leedcode第一题心得--快速排序（超详解）

这里说明，第一题本身不需要这么多代码，以下是为了锻炼算法

以下是快速排序的方法：具体解释和疑惑点可以参考注释，建议看之前先去看看B站的算法解释：

快速排序算法_哔哩哔哩_bilibili

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //先放数字，再排序
        for (int i = m, j = 0; j < n; i++, j++) {
            nums1[i] = nums2[j];
        }
        rank(nums1,0,m+n-1);
    }
    //注意：这里解释为什么要设置两个方法：我们在第一次分区之后，left == right == mid(基准值的索引)
    //然而，我们知道下一步就是递归，那么我们在传入参数的时候，需要上一个数组的原来的left和right，但是现在已变成mid；
    //所以，如果我们设置一个方法rankfirst，进行上一步(也可以理解为第一次)的排序，让他返回mid，这样之前传入的left和right就不变了；

    //那么，既然知道了为什么和疑惑点，那么也可以这样处理：对原来的left和right做备份处理；
    //以上解释解释了下面的问题


    public void rank(int[] nums,int left,int right){
        if(left<right){
            int mid = rankfirst(nums,left,right);
            rank(nums,left,mid - 1);
            rank(nums,mid + 1,right);
        }
    }
    public int rankfirst(int[] nums,int left,int right) {
        int run = nums[left];//默认每次run取到最左边；作为基准值，不可以改变；

        //左右交换各进行一次，不交换或者left<right，那么就一直移动索引，直到满足条件退出循环；

        while (left < right) {
            // 移动右边指针
            while (left < right) {
                if (right >= 0 && nums[right] < nums[left]) {
                    int temp = nums[right];
                    nums[right] = nums[left];
                    nums[left] = temp;
                    break;
                } else {
                    right--;
                }
            }

            // 移动左边指针
            while (left < right) {
                if (left < nums.length && nums[left] > nums[right]) {
                    int temp = nums[left];
                    nums[left] = nums[right];
                    nums[right] = temp;
                    break;
                } else {
                    left++;
                }
            }
        }

        //此时left == right == mid
        //第一次排序结束，此时分为左右两支，左边一定小，右边一定达，再分别对两边进行相同的方式排序
        //问题1：怎么分别对两边的数组排序？
        int mid = left;//或者==right
        return mid;
    }
}