快速排序的一点细节_快速排序的分界线怎么设置

快速排序的执行步骤：
（1）设置一个分界值（从待排序的数组中选），将分界值与数组左端点进行交换并将分界值存储起来。这时左端点就空了出来，从数组的最右边开始找并找到第一个比分界值小的元素，将这个元素放在左端点（注意左端点的元素已经存起来了）。这时右端点空了出来，然后再左端点开始寻找第一个比分界值大的元素，放在右端点。循环执行，最后会空出来一个位置，将分解值放在这个位置。
（2）通过（1），分界值左边都不大于它，右边都不小于它。对分解值得左右部分开别执行（1），当待处理元素个数为1时所有元素都是有序的。

public static int partition(int[] nums, int left, int right){
        //选择左端点为分界值，为了避免退化情况可以随机选择
        int pivot = nums[left];
        while (left < right){
            //从右侧找到比分界值点大的元素
            while (left < right && nums[right] >= pivot) right--;
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot) left++;
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return  left;
    }
    //递归进行分解处理
    public static void quickSort(int[] nums, int left, int right){
        int middle;
        if(left < right){
            middle = partition(nums, left, right);
            quickSort(nums, left, middle - 1);
            quickSort(nums, middle + 1, right);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

开始排序最重要的部分就行使用partition对其进行划分使得左边都小于分界值，右边都大于分界值。这里有两个需要注意的点，在从左边找第一个大于分解值得点或者从右边找第一个小于分界值的点是都需要添加left<right判断条件，否则会出现下标越界。第二点，由于我们从左边找第一个大于分解值得点或者从右边找第一个小于分界值的点，所以两个循环的条件分布是nums[right] >= pivot和nums[left] <= pivot，千万不可nums[right] > pivot和nums[left] < pivot，取否命题得到从左边找到的点满足nums[right] <= pivot和从右边找到的点满足nums[left] >= pivot，这个点条件有重合也就是nums[right] = pivot和nums[left] = pivot，这会导致死循环。如果循环的条件是nums[right] >= pivot和nums[left] < pivot，则分解点左边的点都大于等于分解点，分界点右边的点都小于分界点，反之亦然。