欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

排序算法之——三路快排分析

程序员文章站 2022-06-04 17:36:20
...

引言

快速排序分析中我们探讨了经典快排的实现,且进行了一些小优化。

但是若序列中包含大量重复的元素,这种情况下,快排的性能就不那么理想了。

下面开始学习三路快排的思想吧。

思路

将数组分为三部分,分别对应于小于、等于和大于哨兵元素v的子序列。

排序算法之——三路快排分析

切分方法为从左到右遍历(扫描)数组一次,维护一个指针lt使得a[left..lt-1]中的元素都小于v,一个指针gt使得
a[gt+1..right]中的元素都大于v,一个指针i使得a[lt..i-1]中的元素都等于v,而a[i..gt]中的元素是还未扫描的。

一开始令i = left + 1,对a[i]v进行比较,根据比较情况作出不同的处理:

  • a[i]小于v,将a[lt]a[i]交换,将lti加1;
  • a[i]大于v,将a[gt]a[i]交换,将gt减1;
  • a[i]等于v,将i加1

以上操作会不断缩小gt - i的值,直到i > gt扫描结束。这时就成了上图切分后的情况。

排序算法之——三路快排分析
假定元素数据如上图。

排序算法之——三路快排分析
先让这三个指针就位。我们选取的哨兵元素v为6。

排序算法之——三路快排分析
a[i]=3小于6,交换a[lt]a[i]:6和3,lti指针后移。

排序算法之——三路快排分析

a[i]=8大于6,交换a[gt]a[i]:7和8,gt指针前移。

排序算法之——三路快排分析
a[i]=7大于6,交换a[gt]a[i]:1和7,gt指针前移。

排序算法之——三路快排分析
a[i]=1小于6,交换a[lt]a[i]:6和1,lti指针后移。

排序算法之——三路快排分析
a[i]=2小于6,交换a[lt]a[i]:6和2,lti指针后移。

排序算法之——三路快排分析
a[i]=1小于6,交换a[lt]a[i]:6和1,lti指针后移。

排序算法之——三路快排分析
a[i]=6等于6,i指针后移。直到a[i]=5,交换6和5,lti指针后移。

排序算法之——三路快排分析
i继续后移,然后不满足i <= gt的条件啦,跳出循环~

数组就被分为三部分,分别对应于小于、等于和大约哨兵元素v的子序列。

一次切分就完毕了,接下来只要对小于和大于v的部分进行同样的切分即可。

代码

private static <E extends Comparable<? super E>> void quick3Way(E[] a) {
    shuffle(a);
    quick3Way(a, 0, a.length - 1);
}


/**
 * @param a
 * @param left
 * @param right
 * @param <E>
 */
private static <E extends Comparable<? super E>> void quick3Way(E[] a, int left, int right) {
    if (right <= left) {
        return;
    }
    int lt = left, i = left + 1, gt = right;
    E v = a[left];
    //当 i > gt时跳出循环
    while (i <= gt) {
        int cmp = a[i].compareTo(v);//这里有个坑,注意和普通快排算法不一样,a[left]的元素是会发生变化的,因此需要用临时变量v缓存起来

        if (cmp < 0) {
            //a[i]小于v,将a[lt]和a[i]交换,将lt和i加1;
            swap(a, lt++, i++);
        } else if (cmp > 0) {
            //a[i]大于v,将a[gt]和a[i]交换,将gt减1;
            swap(a, gt--, i);
        } else {
            //a[i]等于v,将i加1
            i++;
        }
    }
    quick3Way(a, left, lt - 1);
    quick3Way(a, gt + 1, right);
}