• 欢迎光临~

快速排序模版

开发技术 开发技术 2022-05-31 次浏览

记录一下快速排序的模版,快排有很多种写法,记一种理解的模版就可以了。 

    public void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }

        int pivot = nums[left];
        int i = left - 1, j = right + 1;
        while (i < j) {
            // 这两个while循环的顺序可以交换,顺序不重要
            while (nums[--j] > pivot) {
            }
            while (nums[++i] < pivot) {
            }
            if (i < j) {
                swap(nums, i, j);
            }
        }
        // 关键点是怎么切分,当退出循环后
        // nums[j]左边的数都小于pivot,nums[i]右边的数都大于pivot
        // 而i和j的关系有两种,要么i=j,要么i=j+1
        // 所以切分时可以用[left,i-1][i,rigjt],和[left,j][j+1,right]这两种
        // 而我们选取的pivot是最左边的数,当pivot一开始就处于正确的位置,即此时i=left时
        // 这时按[left,i-1][i,rigjt]切分就会出现死循环,第二段区间依然是[left, right]
        // 故当我们选取left为pivot时,需要用[left,j][j+1,right]来切分
        // 同理,当我们选取最后一个值为pivot时,需要用i来切分,防止j的位置不变,导致死循环
        quickSort(nums, left, j);
        quickSort(nums, j + 1, right);
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

 

程序员灯塔
转载请注明原文链接:快速排序模版
喜欢 (0)