快速排序算法

题目链接：排序数组

快速排序的思想在于

partion的目标是让比pivot小的元素分布在其左侧，比pivot大的元素分布在其右侧，在排列过程的最后找到一个合适的pivot位置输出。

partion方法1：遇到左边比pivot大的与右边比pivot小时，二者进行交换，最后low==high时就是pivot的位置，交换pivot与low==high的位置上的数即可。

import java.util.Arrays;

class Solution1 {
    public int partition(int[] nums, int low, int high) {
        // select one pivot to sort the array partly
        // and return the position of pivot
        int pos = high;
        int pivot = nums[casualPos];
        while (low < high) {
            while (low < high && nums[low] <= pivot)
                low++;
            while (low < high && nums[high] >= pivot)
                high--;
            swap(nums, low, high);
        }
        swap(nums, pos, high);
        return high;
    }

    public void quicksort(int[] nums, int start, int end) {
        if (start < end) {
            int pivot = partition(nums, start, end);
            System.out.println("pivot=" + pivot);
            Arrays.stream(nums).forEach(System.out::print);
            System.out.println();
            quicksort(nums, start, pivot - 1);
            quicksort(nums, pivot + 1, end);
        }
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void main(String[] args) {
        int[] nums = new int[] {5,7,1,6,4,8,3,2 };
        Solution1 slt = new Solution1();
        slt.quicksort(nums, 0, nums.length - 1);
        for (int i : nums) {
            System.out.println(i);
        }
    }
}

partion中有需要注意的地方，如果pivot一开始选择左侧，则要先high后low；如果pivot一开始选择右侧，则要先low后high，这样才能保证low==high时，交换pivot和pos时不会错。

原因：在low==high的上一步，pivot的位置与low、high三者的位置可能有两种关系：

• pivot的位置在nums[low]和nums[high]的左侧，此时交换nums[low]和pivot就能完成partion过程，只有让high向low移动，然后才可以在low==high时交换pivot和nums[low]；
• pivot的位置在nums[low]和nums[high]的右侧，此时交换nums[high]和pivot就能完成partion过程，只有让low向high移动，然后才可以在low==high时交换pivot和nums[high]。

Note：如果一开始选择中间元素作为pivot并非不可，只是在low==high的上一步，pivot的位置与low、high三者的位置关系就较难确定，不易编码。选择始选择最左或最右元素作pivot更利于思考。

partion方法2：左侧遇到比pivot大的，与pivot交换，右侧遇到比pivot小的，与pivot交换。每次交换后pivot的索引就会变化，下次使用pivot时要先更新索引。待low==high时，pivot已经被排列到合适的位置，就是low==high的位置。

import java.util.Arrays;

class Solution1 {

    public int partition2(int[] nums, int low, int high) {
        // select one pivot to sort the array partly
        // and return the position of pivot
        int pivot = nums[high];
        while (low < high) {
            while (low < high && nums[low] <= pivot)
                low++;
            pivot = nums[high];
            nums[high] = nums[low];
            nums[low] = pivot;
            while (low < high && nums[high] >= pivot)
                high--;
            pivot = nums[low];
            nums[low] = nums[high];
            nums[high] = pivot;
        }
        return high;
    }

    public void quicksort(int[] nums, int start, int end) {
        if (start < end) {
            int pivot = partition2(nums, start, end);
            System.out.println("pivot=" + pivot);
            Arrays.stream(nums).forEach(System.out::print);
            System.out.println();
            quicksort(nums, start, pivot - 1);
            quicksort(nums, pivot + 1, end);
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[] { 5, 7, 1, 6, 4, 8, 3, 2 };
        Solution1 slt = new Solution1();
        slt.quicksort(nums, 0, nums.length - 1);
        for (int i : nums) {
            System.out.println(i);
        }
    }
}

上述代码可以简化，简化后的代码如下。左侧遇到比pivot大的数，该位置的数值赋值到high所在位置，省略对low位置赋值pivot操作（等到最后统一做，此时会会导致low位置的数失效）；右侧遇到比pivot小的数，该位置的数值赋值到low所在位置，省略对high位置赋值pivot操作（等到最后统一做，此时会导致high位置的数失效）。失效的位置实际上是潜在的pivot的位置，即将来可能会被赋值pivot。最后一步是把pivot放到low==high的位置上。

import java.util.Arrays;

class Solution1 {

    public int partition2(int[] nums, int low, int high) {
        // select one pivot to sort the array partly
        // and return the position of pivot
        int pivot = nums[high];
        while (low < high) {
            while (low < high && nums[low] <= pivot)
                low++;
            nums[high] = nums[low];
            while (low < high && nums[high] >= pivot)
                high--;
            nums[low] = nums[high];
        }
        nums[high] = pivot;
        return high;
    }

    public void quicksort(int[] nums, int start, int end) {
        if (start < end) {
            int pivot = partition2(nums, start, end);
            System.out.println("pivot=" + pivot);
            Arrays.stream(nums).forEach(System.out::print);
            System.out.println();
            quicksort(nums, start, pivot - 1);
            quicksort(nums, pivot + 1, end);
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[] { 5, 7, 1, 6, 4, 8, 3, 2 };
        Solution1 slt = new Solution1();
        slt.quicksort(nums, 0, nums.length - 1);
        for (int i : nums) {
            System.out.println(i);
        }
    }
}

简化后的方法其实是一种挖坑法，坑就是被转移走数值的位置上的数，由于坑实际上是未被赋值pivot的位置，所以这个坑可能将来被存放pivot，是pivot潜在的位置。

我感觉方法一易思考和编写，因此将方法一编写在了前面位置，由于没有找到合适的GIF动画讲解方法一，所以给个哔哩哔哩视频的链接，1分11秒开始讲解方法一的partion过程。链接：【理性的设计#01】用10秒，度过30秒时间 - oooooohmygosh

严蔚敏《数据结构》采用的是简化后的方法二，可能是大部分人最先接触的partion方法。