快速排序

发表于 更新于 分类于 阅读次数： 本文字数： 771 阅读时长 ≈ 1 分钟
引言：

速记快速排序

快速排序

优雅的快速排序

更新后的快排，发现之前的快排存在点问题，而且不利于记忆（常见的算法应该很快就能写出来）

1
2
3
4
5
public int[] sortArray(int[] nums) {
    sort(nums, 0, nums.length - 1);
    // 直接传入0和最后一个索引即可
    return nums;
}

快排code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void sort(int[] nums, int i, int j) {
    if (i >= j) return;
    int left = i - 1;
    int right = j + 1;
    int pivot = nums[(i + j + 1) / 2];

    for (; left < right; ) {
        for (; nums[--right] > pivot;);
        for (; nums[++left] < pivot;);
        if(left < right){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
    }
    // 下面这个部分，选择边界要注意：看下文
    sort(nums, i, left - 1);
    sort(nums, left, j);
}

我们知道，快排的pivot选择，一般有三种选法，第一个数字、最后一个数字、中间任意一个数字

上面的代码就选择了中间任意一个数字，如果要选择第一个数字或是最后一个数字，那么他们有如下对应规则：

注意边界问题：pivot选择要注意，其实选择left和right都可以，但是要和初始值对应

  • pivot选择nums[j]：可以选(i, left-1) (left , j)区间
  • pivot选择nums[i]：可以选(i, right), (right + 1, j) 区间