查看“快速排序”的源代码

https://www.bilibili.com/video/BV1at411T75o

《算法：第4版》

[http://www.jihongchang.top/index.php/%E4%BA%A4%E6%8D%A2%E7%B1%BB%E6%8E%92%E5%BA%8F#4%EF%BC%89%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F 软考：程序员中的快速排序]

快速排序的优点：

速度最快，原地排序

算法的时间复杂度是 NlgN

=== 实现 ===

==== 数组版 ====
<syntaxhighlight lang="java">
public class Quick {

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

    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);
    }

    private static int partition(Comparable[] a, int lo, int hi) {
        //将数组切分为a[lo……i-1]，a[i]，a[i+1……hi]
        int i = lo, 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);

        }//end while

        exch(a, lo, j);

        return j;

    }//end partition


    /**
     * 自定义比较规则
     *
     * @param a
     * @param b
     * @return
     */
    private static boolean less(Comparable a, Comparable b) {
        boolean ret = false;
        if (a instanceof Integer && b instanceof Integer) {
            ret = (Integer) a < (Integer) b;
        }
        return ret;
    }

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

    public static void main(String[] args) {
        Integer[] arr = {5,4,6,3,7,2,8,1,9,0};
        Quick.sort(arr);

        System.out.print(arr[0]);

        for (int i = 1; i < arr.length; i++) {
            System.out.printf(", %d", arr[i]);
        }

        System.out.println();
    }

}
</syntaxhighlight>

==== 数组泛型版 ====

==== 列表泛型版 ====

==== 效率增强版列表 ====