常见排序算法

算法	平均时间复杂度	原地排序	稳定排序
插入排序	O(n^2) ，有序情况 -> O(n)	True	True
快速排序	O(nlogn)，有序情况 -> O(n^2)	True	False
归并排序	O(nlogn)	False	True
堆排序	O(nlogn)	True	False

稳定性

对于相等的元素，在排序后，原来靠前的元素依然靠前。

相等的元素位置没有改变。

通过自定义比较器，解决排序算法的稳定性问题。

快速排序

排序算法是最好的排序算法之一，在很多库函数中选择使用快速排序来作为实现方式，如java中的sort()。

工作方式
1.1. 从数组中取出一个元素作为“基准值”。
1.2. 将其他元素分为“大于”基准值的元素和“小于”基准值的元素。
1.3. 递归对这两个组做排序。
最好情况下的复杂度： O(nlogn)。
最坏情况下的复杂度：如果元素接近有序，算法的复杂度接近于 O(n^2)。

快速排序简单实现

java方式实现

    public static void sort(Object[] v, int left, int right, Comparator comparator) {
        int i, last;
        if (left >= right)
            return;
        // move pivot item
        swap(v, left, rand(left, right));
        last = left;
        // partition
        for (i = left + 1; i <= right; i++) {
            if (comparator.compare(v[i], v[left]) < 0) {
                swap(v, ++last, i);
            }
        }
        // restore pivot item
        swap(v, left, last);
        // sort each part
        sort(v, left, last - 1, comparator);
        sort(v, last + 1, right, comparator);
    }

    static void swap(Object[] v, int i, int j) {
        Object temp = v[i];
        v[i] = v[j];
        v[j] = temp;
    }

    static Random random = new Random();
    static int rand(int left, int right) {
        return left + Math.abs(random.nextInt()) % (right - left + 1);
    }