0%

三向切分快排

发表于 更新于 分类于

简介

三向切分快排是针对特殊场景的一种优化，比较适合数组中重复元素比较多的时候。

与标准快速排序分为小于等于基准和大于基准两个部分不同，三向切分分为三个部分，也就是小于基准、等于基准和大于基准，也就是把标准快排的等于部分单独拆分出来，这样这部分相同的数据就不用再次比较了，所以，当重复元素比较多时，将会有比较大的性能提升。

实现

先放代码，后面解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public void threeWayPartition(int[] nums) {
    threeWayPartition(nums, 0, nums.length - 1);
}

private void threeWayPartition(int[] nums, int start, int end) {
    if (start >= end) {
        return;
    }
    int lt = start;
    int eq = start;
    int gt = end;
    int base = nums[eq];
    while (eq <= gt) {
        if (nums[eq] > base) {
            swap(nums, eq, gt);
            gt--;
        } else if (nums[eq] < base) {
            swap(nums, lt, eq);
            lt++;
            eq++;
        } else {
            eq++;
        }
    }
    threeWayPartition(nums, start, lt - 1);
    threeWayPartition(nums, gt + 1, end);
}

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

代码的核心是while循环，主要涉及三个索引变量lt、eq、gt

三个变量可以将数据分为四个部分，除了结果的小于、等于、大于外，还有过程中的未比较部分

也就是

  • [start-lt) 代表小于基准的数据
  • [lt-eq) 代表等于基准的数据
  • [eq-gt] 代表未比较的数据
  • (gt-end] 代表大于基准的数据

其中，小于和等于在前半部分，大于在后半部分，为比较在中间，随着比较的进行，小于等于的向后扩展，大于的向前扩展，慢慢吃掉未比较的区域

初始时，所有的数据[start-end]都是未比较的，小于、等于、大于基数的数据都没有，所以lt、eq初始化为0，gt初始化为end

我们先将基准定义为开始第一个元素

我们遍历未比较的数据，也就是[eq-gt]

从第一个元素nums[eq]开始

由于基数就是第一个，自己和自己肯定相等，所以执行else逻辑，也就是和基数相等，相等时，等于基准的数据多了一个，eq索引后移

接下来第二个数与基准元素比较，如果这个数比基准元素大，我们是要把它放到数组的第三部分的，也就是(gt-end]区域，区域不包含qt，也意味着gt代表下一个大于基准的数将要被放入的位置，此时nums[eq]比基准大，所以两数交换位置，交换完成后，大于基准的数多了一个，所以gt前移，而eq位置的数据是从原来的qt来的，还是未比较的，所以eq的位置不动，还需要继续比较

如果num[eq]比基准元素小，我们要把它放入[start-lt)区域，同样，区域不包含lt，lt是下一个比基准小的数的位置，所以交换eq和lt位置的数据，将小于基准的数，也就是num[eq]放到lt那里，此时小于基数的数多了一个，lt前移；由于原始lt放的是等于基准的数据（[lt-eq)），现在到eq这个位置来了，已经不需要再次比较了，相当于把“等于基准的数据”这个集合的第一个数挪到了最后的位置，数量不变，虽然数量不变，但是由于这个集合的位置是在小于基准那个集合的后面，小于基准的集合多了一个，所以eq也要同步后移

继续以相同的逻辑遍历

直到没有未比较的数据，也就是[eq-gt]这个集合为空，所以退出条件是gt > eq

经过一轮遍历后，数组被分为三个部分

也就是

  • [start-lt) 代表小于基准的数据
  • [lt-eq) 代表等于基准的数据
  • (gt-end] 代表大于基准的数据

[eq-gt]已经没有了

等于基准的数据已经不需要再排序了，小于和大于的都只是比基准大或小，内部并不一定有序，所以继续对两个区域用相同的逻辑进行排序

标准快排，只是基准那一个数不需要下次的排序，而不是等于基准的一批数，如果等于基准的数很多，就会造成浪费，而三向切分就是针对这种情况的一个优化。