基础算法-快速排序

今天学习另外一种更加常用的排序算法：快速排序。

题目介绍

还是使用之前的题目：给定一个数组，将数组按从小到大顺序排序。题目理解起来也是很容易的，就不再画图介绍了。

归并排序

快速排序的核心思想是，在数组中随机选择一个元素，然后遍历数组，将小于该元素的移动到元素左边，大于该元素的移动到元素的右边。
然后再分别递归对左右两边的数组进行排序，最终当待排序只有一个元素时退出递归。

实现代码

因在之前文章实现过排序抽象类，因此快速排序类只要继承抽象类即可。

public class Quick extends AbstractSort {

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

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

    private int partition(Comparable[] a, int lo, int 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);
        }
        exch(a, lo, j);
        return j;
    }
}

算法相关实现源码地址：https://github.com/xiekq/rubs-algorithms