排序算法-快速排序

思路:

• 设待排序数组长度为n

1. 选取边界l,r为数组左右边界0~n-1
2. 每次于一边界范围中选取一数组元素i,将小于i的数置于数组左边,大于i的数置于数组右边.
   每次步骤2都将固定一个数组元素i
3. 分别对2操作后的i左右两侧数组元素进行2操作,可分别得到子数组与新固定元素
   (注:元素i处位置已经固定,下次循环时不需考虑i的下标)
4. l>=r时结束本次固定

优化:

快排关键在于选取基准值i,若待排序数组本身即有序则快排会退化为冒泡排序.
选取基准值时我们可以随机地选取l~r处的下标将其作为本次快排基准值
方法:index = l + (int)(Math.random() * (r - l + 1))

public void quickSort_1(int[] nums, int l, int r){
    if(l >= r) return;
    int l1 = l, r1 = r;
    int index = l + (int)(Math.random() * (r - l + 1));
    swap(nums, l, index);
    while(l1 < r1){
        while(l1 < r1 && nums[l] <= nums[r1]) r1--;
        while(l1 < r1 && nums[l] >= nums[l1]) l1++;
        swap(nums, l1, r1);
    }
    swap(nums, l1, l);
    quickSort_1(nums, l, l1 - 1);
    quickSort_1(nums, l1 + 1, r);
}

private void swap(int[] nums, int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

排序算法-快速排序

原文：https://www.cnblogs.com/jingqz/p/15136973.html