1.快速排序

快速排序，简称快排。

快速排序是一种较快的交换排序算法。目前，仍被认为是最快的内排序算法。

2.快排的过程

快排的基本思想是：在待排序列中选择一个元素，以该元素为标准，将整个序列分为两组，第一组都小于该标准元素，第二组都大于该标准元素。第一组放在该元素的前面，标准元素放在中间，第二组放在该元素的后面。然后对第一组和第二组元素执行上述步骤。

很明显快排是一个递归的过程。

下面，图示快排过程。

（1）准备一个无序序列，将首元素标记为left，将最后一个元素标记为right。

将mid初始化为left执行的元素。

（2）从后向前过滤（right递减），直到找到a[right] < a[mid]的元素，定为乱序元素

（3）将乱序元素与mid指向的元素交换。

mid指向的元素切换为right指向的元素，left不动。

（4）从前向后过滤（left递增），直到找到a[left] > a[mid]的元素，定为乱序元素

（5）将乱序元素与mid指向的元素交换。

mid指向的元素切换为left指向的元素，right不动。

（6）重复执行（2）到（5）的操作，直到right、left和mid都指向同一个元素。

至此，找到了mid元素正确的位置。

（7）找到mid的正确位置后，表示mid指向的元素次序正确，位置将不再改变。然后分别递归排序mid左边序列和mid右边序列。

递归过程就是重复执行（1）到（6）的过程。

（8）所有递归结束后，排序结束。

3.快排时间复杂度

最好的情况下，时间复杂度为O(NlogN)。

最坏的情况下，事件复杂度退化为O(N^2)。

平均时间复杂度为O(NlogN)。

4.快排代码实现

以下是Java实现版本：

    public void quickSort(T[] a, int left, int right) {
        int mid;
        if (left >= right) {
            return;
        }
        mid = divide(a, left, right);
        quickSort(a, left, mid - 1);
        quickSort(a, mid + 1, right);
    }

    public int divide(T[] a, int left, int right) {
        T tmp = a[left];
        do {
            while (left < right && a[right] >= tmp) {
                --right;
            }
            if (left < right) {
                a[left] = a[right];
                left++;
            }
            while (left < right && a[left] <= tmp) {
                ++left;
            }
            if (left < right) {
                a[right] = a[left];
                --right;
            }
        } while (left != right);
        a[left] = tmp;
        return left;
    }