排序算法07：三向快速排序

2017-04-30 本文已影响93人梦中人在梦中

算法介绍

在上一篇<a href="http://muchstudy.com/2017/04/29/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%9506%EF%BC%9A%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F/">排序算法06：快速排序</a>中，可以知道，快速排序不停的递归切分数组。在有大量的重复元素情况下，这样的切分存在巨大的改进空间。三向切分的快速排序就是为了提升在有大量重复元素情况下快速排序的性能。

快速排序把数组切分为两部分，分别对应与小于，大于切分元素的数组元素。而三向切分将数组切分为三部分，分别对应小于，等于，大于切分元素的数组元素。

三向切分的快速排序的算法逻辑为：从左到右遍历数组一次，维护一个指针lt使得a[lo..lt-1]中的元素都小于v，一个指针gt使得a[gt+1..hi]中的元素都大于v，一个指针i使得a[gt..i-1]中的元素都等于v,a[i..gt]中的元素都还未确定。

三向切分的示意图：

三向切分的示意图

算法实现

function quick3way(a,lo,hi) {
        if(hi<=lo){return;}
        var lt=lo,i=lo+1,gt=hi;
        var v = a[lo];              //- 选择a[lo]为需要切分的元素
        while (i<=gt){
            if(a[i] < v){
                exch(a,lt++,i++)
            }else if(a[i] > v){
                exch(a,i,gt--);
            }else{
                i++;
            }
        }
        /*程序运行到这里结果为:a[lo..lt-1] < v < a[gt+1,hi];其中v=a[lt..gt]*/
        quick3way(a,lo,lt-1);       //- 对左侧（a[lo..lt-1]）进行排序
        quick3way(a,gt+1,hi);       //- 对右侧(a[gt+1,hi])进行排序
    }

三向切分的轨迹：

三向切分的轨迹

完整代码

Javascript实现

/**
 * Created by YiYing on 2017/4/30.
 */
(function (W) {
    function quick3way(a,lo,hi) {
        if(hi<=lo){return;}
        var lt=lo,i=lo+1,gt=hi;
        var v = a[lo];              //- 选择a[lo]为需要切分的元素
        while (i<=gt){
            if(a[i] < v){
                exch(a,lt++,i++)
            }else if(a[i] > v){
                exch(a,i,gt--);
            }else{
                i++;
            }
        }
        /*程序运行到这里结果为:a[lo..lt-1] < v < a[gt+1,hi];其中v=a[lt..gt]*/
        quick3way(a,lo,lt-1);       //- 对左侧（a[lo..lt-1]）进行排序
        quick3way(a,gt+1,hi);       //- 对右侧(a[gt+1,hi])进行排序
    }

    /**
     * 交换数组中m与n的位置
     * @param a  数组
     * @param m
     * @param n
     */
    function exch(a,m,n) {
        var swap    = a[m];
        a[m] = a[n];
        a[n] = swap;
    }

    W.Quick3way = function (a) {
        quick3way(a,0,a.length-1);
    }
})(window);

//测试代码
(function () {
    var chars = ['0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'];
    var arr = [];
    for(var i=0;i<1000000;i++){
        var id = Math.ceil(Math.random()*35);
        arr[i] = chars[id];
    }

    console.time("Quick3way");
    Quick3way(arr);      //- chrome下一百万数据平均120ms,明显优于快速排序
    console.timeEnd("Quick3way");
})();

Java实现


package com.algs;

/**
 * 三向快速排序（适用于重复元素较多的情况）
 * @author YiYing
 * @data 2017年4月30日 下午10:34:09
 */
public class Quick3way {

    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int lt = lo, gt = hi;
        Comparable v = a[lo];
        int i = lo;
        while (i <= gt) {
            int cmp = a[i].compareTo(v);
            if      (cmp < 0) exch(a, lt++, i++);
            else if (cmp > 0) exch(a, i, gt--);
            else              i++;
        }

        //此时数组中的情况为：a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
        sort(a, lo, lt-1);      //- 对左侧进行排序
        sort(a, gt+1, hi);      //- 对右侧进行排序
    }


    //交换 a[i]和a[j]的位置
    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    public static void show(Integer[] a){
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }
    public static void main(String[] args) {
        Integer[] arr = {4,5,6,0,3,5,21,7,9,0,1};
        Quick3way.sort(arr,0,arr.length-1);
        Quick3way.show(arr);
    }
}

总结

不稳定。
原地排序。
时间复杂度为介于N到NlogN之间
空间复杂度为lgN
经测试验证，在存在大量重复元素情况下，三向切分的快速排序的平均排序时间明显快于快速排序

GitHub：https://github.com/AlbertKnag/algs-practice

上一篇：<a href="http://muchstudy.com/2017/04/29/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%9506%EF%BC%9A%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F/">排序算法06：快速排序</a>
下一篇：<a href="http://muchstudy.com/2017/05/01/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%9508%EF%BC%9A%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97%E4%B8%8E%E5%A0%86%E6%8E%92%E5%BA%8F/">排序算法08：优先队列与堆排序</a>