快速排序（Quick Sort）

通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序的目的。

枢轴（pivot）

先选取序列当中的一个关键字，想尽办法将其放在一个位置，使得它左边的值都比它小，右边的值都比它大，我们将这样子的关键字称为枢轴。

函数构成

partition
选出枢轴，将比枢轴小的数字放在左边，将比枢轴大的数字放在右边，所有坐标遍历之后，返回此时枢轴的坐标
swap
交换两个坐标的值

算法图解

以{50,10,90,30}的数组为例，以下是首次交换的过程图解

快速排序.jpeg

代码(java)实现

public class QuickSortDemo {
    public static void main(String[] args) {
        int[] list = {50, 10, 90, 30, 70, 40, 80, 60, 20};
        quickSort(list);

        for (int a : list) {
            System.out.println(a);
        }
    }

    private static void quickSort(int[] list) {
        if (list == null || list.length == 0) {
            return;
        }

        qSort(list, 0, list.length - 1);
    }

    private static void qSort(int[] list, int low, int high) {

        if (low < high) {
            int pivot = partition(list, low, high);
            qSort(list, low, pivot - 1);
            qSort(list, pivot + 1, high);
        }

    }

    /**
     * 我们这里以list[low]作为参考,所以一定要先从high开始进行交换
     * @param list
     * @param low
     * @param high
     * @return
     */
    private static int partition(int[] list, int low, int high) {
        int pivotKey = list[low];

        while (low < high) {

            while (low < high && list[high] >= pivotKey) {
                high--;
            }
            swap(list, low, high);

            while (low < high && list[low] <= pivotKey) {
                low++;
            }
            swap(list, low, high);

        }

        return low;
    }

    /**
     * 交换两个坐标的值
     * @param list
     * @param index1
     * @param index2
     */
    private static void swap(int[] list, int index1, int index2) {
        int data = list[index1];
        list[index1] = list[index2];
        list[index2] = data;
    }
}

复杂度分析

最优时间复杂度：O(nlogn)
最坏时间复杂度：O(n^2)
平均时间复杂度：O(nlogn)

最优空间复杂度：O(logn)
最坏空间复杂度：O(n)
平均空间复杂度：O(logn)

总结

快速排序是一种不稳定的排序方法。

优化

优化选取枢轴的方式

1.随机选取枢轴法
2.三数取中（median-of-three）
方法：取三个关键字先进行排序，将中间数作为枢轴，一般是取左端，右端，中间三个数。
适用条件：待排序序列比较小
3.九数取中（median-of-nine）
方法：先从数组中分三系取样，每次取三个数，三个样品各取出中数，然后从这三个中数当中再取出一个中数作为枢轴。

优化不必要的交换

优化小数组时的排序方案

在数组非常大的情况下，其实快速排序的递归性能影响相对于它的整体算法优势而言时可以忽略的；
在数组非常小的情况下，其实快速排序反而不如直接插入排序来的更好（直接插入排序时简单排序中性能最好的）。

针对以上这种情况，我们为算法设置一个阈值（有资料认为是7也有资料认为是50），当数组的大小不大于这个值的时候，我们选择直接插入排序，当数组的大小大于这个值的时候，我们就选择快速排序，这样就能保证最大化的利用这两种排序的优势来完成排序工作。

优化递归操作