快速排序

简介

快速排序是使用分治思想进行排序的一种方法，其平均效率较高，故被经常使用。一般来说，快速排序的平均算法复杂度是，最差情况下的算法复杂度为。

基本思想

1.先从数列里取出一个数作为基准，一般取列表中的第一个数字
2.从数列首尾遍历，将比基准数大的数字放到其右边，将比基准数字小的数字放到左边
3.基准数字位置确定，在其左边区域和右边区域递归2中的操作，直到各区间只有一个数

基本代码

package quick.sort;

import edu.princeton.cs.algs4.StdRandom;

public class Quick {
    private static int partition(Comparable[] a, int lo, int hi){

        int i = lo, j = hi + 1;
        while (true){

            while (less(a[++i], a[lo]))
                if (i == hi) break;

            while(less(a[lo], a[--j]))
                if(j == lo) break;

            if (i >= j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }

    private static void sort(Comparable[] a, int lo, int hi){
        if (lo >= hi) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j+1, hi);
    }

    public static void sort(Comparable[] a){
        // shuffle函数将数列中的数字顺序打乱，防止数列有序，增加算法复杂度
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
    }

    private static void exch(Comparable[] a, int i, int j) {
        Comparable swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

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