排序算法06：快速排序

2017-04-29

算法介绍

快速排序是一种分治的排序算法。排序逻辑为：先挑一个元素来切分数组，最终让该元素的左侧都小于该元素，右侧的所有元素都大于该元素。递归的让左侧和右侧分别执行该操作，最终让整个数组变得有序。

快速排序示意图：

咋眼一看快速排序跟归并排序很像，其实区别挺明显的。归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当左右两个数组有序时整个数组为自然有序状态。

快速排序的切分

快速排序的核心在于数组的切分。切分的逻辑为，维护两个指针i和j，i从前往后移动，j从后往前移动。最终让切分元素的左侧都小于切分元素，右侧都大于切分元素。

切分示意图如下：

Javascript代码如下：

/**
     * 将数组a切分为a[lo...i-1],a[i],a[i+1,hi]
     * @param a     需要切分的数组
     * @param lo    起始位置
     * @param hi    结束位置
     */
    function partition(a,lo,hi) {
        var i = lo,j=hi+1;      //- i,j为左右扫描的指针
        var v = a[lo];          //- 选择第lo元素为切分元素，让lo左边的都小于a[lo],右边的都大于a[lo]
        while(true){
            //不断从前向后移动指针
            while (a[++i] < v){
                if(i==hi){break;}
            }
            //不断的从后往前移动指针
            while (v < a[--j]){
                if(j==lo){break;}
            }
            if(i>=j){break;}
            //较小的往前放，较小的往后放
            exch(a,i,j);
        }
        //把切分的元素放到正确的位置，交换lo与j的位置
        exch(a,lo,j);
        return j;
    }

一次切分的切分轨迹如下：

排序实现

切分完成了排序就比较简单了，代码如下：

/**
 * 快速排序
 * @param a     需要排序的数组
 * @param lo    起始位置
 * @param hi    结束位置
 */
function sort(a,lo,hi) {
    if(hi<=lo)return;
    var j = partition(a,lo,hi); //- 切分数组，让a[j]左边的都小于它，右边的都大于它。
    sort(a,lo,j-1);             //- 将左半部分a[lo..j-1]排序
    sort(a,j+1,hi);             //- 将右半部份a[j+1...hi]排序
}

完整代码

Javascript实现


/**
 * Created by YiYing on 2017/4/30.
 */

(function (W) {
    /**
     * 快速排序
     * @param a     需要排序的数组
     * @param lo    起始位置
     * @param hi    结束位置
     */
    function sort(a,lo,hi) {
        if(hi<=lo)return;
        var j = partition(a,lo,hi); //- 切分数组，让a[j]左边的都小于它，右边的都大于它。
        sort(a,lo,j-1);             //- 将左半部分a[lo..j-1]排序
        sort(a,j+1,hi);             //- 将右半部份a[j+1...hi]排序
    }

    /**
     * 将数组a切分为a[lo...i-1],a[i],a[i+1,hi]
     * @param a     需要切分的数组
     * @param lo    起始位置
     * @param hi    结束位置
     */
    function partition(a,lo,hi) {
        var i = lo,j=hi+1;      //- i,j为左右扫描的指针
        var v = a[lo];          //- 选择第lo元素为切分元素，让lo左边的都小于a[lo],右边的都大于a[lo]
        while(true){
            //不断从前向后移动指针
            while (a[++i] < v){
                if(i==hi){break;}
            }
            //不断的从后往前移动指针
            while (v < a[--j]){
                if(j==lo){break;}
            }
            if(i>=j){break;}
            //较小的往前放，较小的往后放
            exch(a,i,j);
        }
        //把切分的元素放到正确的位置，交换lo与j的位置
        exch(a,lo,j);
        return j;
    }

    /**
     * 交换数组中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.QuickSort = function (a) {
        sort(a,0,a.length);
    }
})(window);

//测试代码
(function () {
    //var arr = [4,5,6,0,3,5,21,7,9,0,1];
    //console.log(arr);
    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("QuickSort");
    QuickSort(arr);      //- chrome下一百万数据平均250ms,如果不计算长度，则小于200ms
    console.timeEnd("QuickSort");
})();

Java实现


package com.algs;


public class Quick {

	public static void sort(Comparable[] a) {
        sort(a, 0, a.length - 1);
    }

	//让数组从a[lo] 到 a[hi]有序
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j+1, hi);
    }

	// 切分数组a[lo..hi] 最终让数组满足如下状态： a[lo..j-1] <= a[j] <= a[j+1..hi]
    // 并返回j
    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        Comparable v = a[lo];
        while (true) {
            while (less(a[++i], v))
                if (i == hi) break;
            while (less(v, a[--j]))
                if (j == lo) break;
            if (i >= j) break;
            exch(a, i, j);
        }
        // 把切分的元素放到j的位置上
        exch(a, lo, j);
        return j;
    }

     // 判断v < w ?
     private static boolean less(Comparable v, Comparable w) {
         return v.compareTo(w) < 0;
     }

     // 交换 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[] a = {1,55,32,2,3,4};
		sort(a);
		show(a);
	}

}

总结

不稳定。
原地排序。
时间复杂度为NlogN
空间复杂度为lgN
快速排序最好的情况是每次都正好能将数组对半分
如果使用左右两个辅助数组可以方便实现切分，但把数组复制回去的成本会大大降低排序的速度
归并排序和希尔排序一般都比快速排序慢。原因为：快速排序切分中用一个递增的索引将数组元素和一个定值比较。而归并排序和希尔排序在内循环中移动数据的频率较高。

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

上一篇：排序算法05：归并排序
下一篇：排序算法07：三向快速排序