排序----快速排序

数据结构与算法

哨兵，，。

public class Solution {
    public void quickSort(int[] nums, int left, int right) {
        if (left > right) {
            return;
        }
        int base = nums[left];
        //i=left+1，会溢出时因为最后left=right,又会打乱顺序，所以把基准数拍进去
        int i = left;
        int j = right;
        //全程i和j是井水不犯河水的
        while (i < j) {
            //在内部是很可能i==j
            while (nums[j] >= base && i < j) {
                j--;
            }
            while (nums[i] <= base && i < j) {
                i++;
            }
            if (i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        nums[left] = nums[i];
        nums[i] = base;
        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 55, 6, 3, 2, 4, 5, 6, 8, 9, 0};
        Solution solution = new Solution();
        solution.quickSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
}

最后的结局是j会一路减小到值为i，但是都没有发生突发事件，于是说明我们的顺序已经排好了，完美收工。快速排序把数组从某个元素分为两部分。但这两部分均是无序的。于是递归两部分，目的是为了拿到分组的标准，。，。直到后面结束的时候一个元素就是一组。与归并不同的是他要中间的数。而归并必须把中间的数划到其中一部分中。