快速排序(Quick-Sort)

1. 简介

快速排序是由C.A.R.Hoare在1960年发明的。快速排序可能是应用最广泛的排序算法了，快速排序的实现简单，平均时间复杂度是O(NlgN)，而且它是原地排序。其实在快排的实现有一些坑，如果不仔细一点，快排也许就变成慢排了。
接下来所讲的排序都是从小到大排序的，代码也是java描述的：

与归并排序一样，快速排序也采用了分而治之的思想。

1. 在数组中选取一个元素作为主元
2. 将数组切分成左右两半，左边一半的元素小于等于主元，右边一半的元素大于等于主元
3. 将左边排序
4. 将右边排序
5. 因为左边已经小于等于右边了，所以当左右两边都排完序，整体也就有序了

2. 代码实现

public class QuickSort {

    //交换数组中两个元素的位置
    private static void swap(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    //切分数组的函数
    private static int partition(Comparable[] a, int left, int right){
        swap(a, (left + right) / 2, left);
        Comparable v = a[left];  //v是主元
        int i = left, j = right + 1;
        
        while (true) {
            while (a[++i].compareTo(v) < 0)
                if (i == right)
                    break;

            while (a[--j].compareTo(v) > 0)
                if (j == left)
                    break;

            if (i < j)
                swap(a, i, j);
            else
                break;
        }
        swap(a, j, left);
        return j;
    }

    private static void sort(Comparable[] a, int left, int right){
        if (left >= right) 
            return;
        int i = partition(a, left, right);  //切分数组，返回切分的位置，也就是主元的位置
        sort(a, left, i - 1);   //对数组的左半边排序
        sort(a, i + 1, right);  //对数组的右半边排序
    }

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


    //测试
    public static void main(String[] args) {
        Integer[] a = new Integer[]{1, 3, 4, 7, 9, 2};
        sort(a);
    }
}

辅助函数：
这一段是快速排序的简单实现，还有一些可以优化的地方。先来介绍一下实现过程需要用的辅助函数：

• 因为排序过程中需要与主元进行比较且参与排序的元素是类变量，所以要求排序的元素需要实现Comparable接口重写compareTo()函数。
• 在与主元比较后可能需要交换位置所以用一个swap()函数交换两个元素的位置。

3. 快速排序性能与复杂度分析

快速排序的运行时间取决于切分是否平衡，而是否平衡又依赖于切分的元素，也就是主元的选择。

• 最坏情况
  假设我们每次选择的主元恰好是待排数组中的极值且元素都不重复时，例如最小值：根据切分函数，指针i在遇到第一个元素就停下来，而j却一直向左遍历直到遇到主元才停下来。最终切分的位置变成了left，切分出一个大小为0的数组和一个大小为n - 1的数组，不烦假设每次都出现这种不平等的切分，切分的操作时间复杂度为O(n)，对一个大小为0的数组递归调用排序会直接返回，因此T(0) = O(1)。于是算法的运行时间的递归式可表达为：T(n) = T(0) + T(n - 1) + O(n) = T(n - 1) + O(n)，T(n)的解是O(n^2)。
• 最好情况
  最好的情况是每次切分后的两个数组大小都不大于n / 2时，这时一个的数组的大小为[n / 2 - 1]，另一个为[n / 2]，此时算法运行时间的递归式为：T(n) = 2T(n / 2) + O(n)，T(n)的解是O(nlgn)。
• 平均情况
  快速排序的平均运行时间其实更接近与最好情况，而非最坏情况。

4. 算法优化

1. 切换到插入排序

• 对于小数组，快速排序比插入排序慢
• 因为递归，快速排序的sort()方法在小数组中也会调用自己

所以可以当数组在大小在M以内时调用插入排序，M的取值可以是5 ~ 15。

2. 选择合适的主元
如我上面所说，假设我们每次选择的主元恰好是待排数组中的极值时，那就是最坏的情况，如果要避免这种情况的发生，那就是要选择合适的主元。我们可以在待排数组取左，中，右3个数，取其中位数作为主元。这样就可以在一定程度上避免最坏情况。

3. 重复的元素不必排序
当数组中存在大量的重复元素时，如果我们用上面所实现的快排，时间复杂度还是要O(nlgn)，这开销是在太大相对于插入排序来说。这时我们可以采用三向切分来实现快排。如下所示：

    left part           center part                   right part
* +--------------------------------------------------------------+
* |  < pivot   |          ==pivot         |    ?    |  > pivot  |
* +--------------------------------------------------------------+
*              ^                          ^         ^
*              |                          |         |
*              lt                         i        gt

通过维持三个指针来控制[left, lt )小于主元(pivot)，[lt, i)等于主元，[i, gt]未知，(gt, right]大于主元。
一开始，lt指向主元的位置left，gt指向right，而i从left右边接下来的第一个索引开始遍历，每当遇到一个数，就判断它与主元之间的大小关系，有三种情况：

• 小于主元就把这个数与lt指向的数交换，然后lt,i都自增1，然后继续遍历
• 大于主元就把这个数与gt指向的数交换，gt自减1，此时i还得不能自增，因为它不知道gt用一个什么样的元素跟它交换，所以留到下一次循环判断交换过来的这个元素的去留
• 等于主元就不用跟谁进行交换，直接自增1就可以

三向切分快速排序如下：

public class Quick {

    //获取中位数
    private static int getMedian(Comparable[] a, int i, int j, int k){
        return a[i].compareTo(a[j]) > 0
                ? (a[i].compareTo(a[k]) < 0 ? i : a[j].compareTo(a[k]) > 0 ? j : k)
                : (a[i].compareTo(a[k]) > 0 ? i : a[j].compareTo(a[k]) < 0 ? j : k);
    }

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

  //插入排序
    private static void insertSort(Comparable[] a, int left, int right) {
        for (int i = left; i <= right; ++i) {
            int j;
            Comparable value = a[i];
            for (j = i - 1; j >= left && value.compareTo(a[j]) < 0; --j)
                a[j + 1] = a[j];
            a[j + 1] = value;
        }
    }

    private static void sort(Comparable[] a, int left, int right){
        if (right - left < 15) {
            insertSort(a, left, right);
            return;
        }
        swap(a, getMedian(a, left, (left + right) / 2, right), left);
        Comparable v = a[left];
        int lt = left, i = left + 1, gt = right;

        while (i <= gt){
            int cmp = a[i].compareTo(v);
            if (cmp < 0)
                swap(a, lt++, i++);
            else if (cmp > 0)
                swap(a, i, gt--);
            else
                i++;
        }

        sort(a, left, lt - 1);
        sort(a, gt + 1, right);
    }
  
   public static void sort(Comparable[] a){
        sort(a, 0, a.length - 1);
    }

//测试
    public static void main(String[] args) {
        int size = 10000000;
        Integer[] a = new Integer[size];
        for (int i = 0; i < 10000000; ++i)
            a[i] = 88;
        sort(a);  
    }
}

5. 注意：

目前所实现的三向切分并不完美，虽然它解决了大量重复元素的不必要排序，将排序时间从线性对数级别降到线性级别，但它在数组元素重复不多的情况下，它的交换次数比标准的二分法多很多。不过在90年代J.Bently和D.Mcllroy找到一个聪明的办法解决了这个问题。接下来的快速三向切分就是解决办法。

快速的三向切分

*   left part         center part                  right part
* +----------------------------------------------------------+
* | == pivot |  < pivot  |    ?    |  > pivot    | == pivot |
* +----------------------------------------------------------+
*            ^           ^         ^             ^
*            |           |         |             |  
*            p           i         j             q

在这个算法中，[p, i)里面的元素小于主元，(j, q]里面的元素大于主元，而左右两端[left, p)和(q, right]等于主元。在算法一开始，p 和 i都指向left后面的第一个元素， j和q都指向right，先把i从左到右遍历时每遇到一个元素都会有三种情况：

• 等于主元，这时只要与p指向的元素交换然后各自自增1即可
• 小于主元，这就是指针p和i所要维护的元素，直接把i自增1跳过就可以
• 大于主元，这时就是j和q所要维护的元素，先退出循环等待与他们交换

同理，对于j从right向左遍历也是一样。当 i > j 时，切分也就结束，最后还要把数组调整为左边小右边大，中间等于主元的形式，再依次排序左边和右边。在这个算法中，既解决了重复元素排序的问题，又解决了少量元素重复时，交换次数过多的问题。接下来是我的实现，不过我觉得我有些地方实现的不太好，凑合着用吧。

快速的三向切分的实现

public class Quick3WayPartitionSort {
    //获取中位数
    private static int getMedian(Comparable[] a, int i, int j, int k){
        return a[i].compareTo(a[j]) > 0
                ? (a[i].compareTo(a[k]) < 0 ? i : a[j].compareTo(a[k]) > 0 ? j : k)
                : (a[i].compareTo(a[k]) > 0 ? i : a[j].compareTo(a[k]) < 0 ? j : k);
    }

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

    public static void insertSort(Comparable[] a, int left, int right) {
        for (int i = left; i <= right; ++i) {
            int j;
            Comparable value = a[i];
            for (j = i - 1; j >= left && value.compareTo(a[j]) < 0; --j)
                a[j + 1] = a[j];
            a[j + 1] = value;
        }
    }
    
    //调整数组
    private static void adjust(Comparable[] a, int start, int end, int toStart){
        for (int i = start; i <= end; ++i)
            swap(a, i, toStart++);
    }

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

    private static void sort(Comparable[] a, int left, int right){
        if (right - left < 10) {
            insertSort(a, left, right);
            return;
        }
        swap(a, getMedian(a, left, (left + right) / 2, right), left);
        Comparable v = a[left];
        int p = left + 1, i = p, j = right, q = j;

        while (true){
            while (i <= j){
                int cmp = a[i].compareTo(v);
                if (cmp == 0)
                    swap(a, i++, p++);
                else if (cmp < 0)
                    i++;
                else
                    break;
            }

            while (i <= j){
                int cmp = a[j].compareTo(v);
                if (cmp == 0)
                    swap(a, j--, q--);
                else if (cmp > 0)
                    j--;
                else
                    break;
            }

            if (i < j)
                swap(a, i++, j--);
            else
                break;
        }

        if (p - left > i - p)
            adjust(a, p, i - 1, left);
        else
            adjust(a, left, p - 1, left + i - p);

        if (right - q > q - j)
            adjust(a, j + 1, q, right - q + j);
        else
            adjust(a, q + 1, right, j + 1);

        sort(a, left, left + i - p - 1);
        sort(a, right + j - q - 1, right);
        }


    public static void main(String[] args) {
        
    }
}

6. 最后

快速排序不是稳定的排序算法，所谓稳定就是当待排数组中存在重复元素的时候，排序后重复元素的相对顺序不会改变。在多关键字排序时，稳定的排序算法就很有用处。比如当一个学生按照学号先排序，然后再根据成绩进行排序，因为成绩存在重复的值，此时稳定的排序算法就会导致排序后具有相同成绩的学生按照学号排序，不会混乱。