清晰易懂学透快速排序（算法村第十关青铜挑战）

全网最清晰快速排序，看完快排思想和代码全部通透，不通透你打我！_哔哩哔哩_bilibili

public static void quickSort(int[] nums, int low, int high)
{
    if (low >= high)
        return;

    //排序，并获取基准值的位置
    int pivotPos = partition(nums, low, high);

    //对左右两个子序列进行快排
    quickSort(nums, low, pivotPos - 1);
    quickSort(nums, pivotPos + 1, high);
}

public static int partition(int[] nums, int low, int high)
{
    //取（子）序列第一个元素为基准元素
    int pivot = nums[low];  //此时 low 为坑位

    while (low < high)
    {
        //先从右边找，填补左边的坑位
        while (low < high && nums[high] >= pivot)
            high--;
        nums[low] = nums[high]; //而后 high 成了坑位

        //再从左边找，填补右边的坑位
        while (low < high && nums[low] <= pivot)
            low++;
        nums[high] = nums[low];
    }

    nums[low] = pivot; //或 nums[high] = pivot
    return low; //或 return high
}

//Text
public static void main(String[] args)
{
    //测试数组为空
    int[] nums1 = {};
    quickSort(nums1, 0, nums1.length - 1);
    System.out.println(Arrays.toString(nums1));

    //测试数组无序
    int[] nums2 = {5, 1, 8, 2, 7};
    quickSort(nums2, 0, nums2.length - 1);
    System.out.println(Arrays.toString(nums2));

    //测试数组逆序
    int[] nums3 = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    quickSort(nums3, 0, nums3.length - 1);
    System.out.println(Arrays.toString(nums3));

    //测试数组有序
    int[] nums4 = {-1, -2, -3, 0, 1, 2, 3};
    quickSort(nums4, 0, nums4.length - 1);
    System.out.println(Arrays.toString(nums4));

    //测试数组有相同元素
    int[] nums5 = {-1, -2, -2, -2, 4, 4, 56, 2};
    quickSort(nums5, 0, nums5.length - 1);
    System.out.println(Arrays.toString(nums5));
}