基本概念

快速排序（Quicksort）是对冒泡排序算法的一种改进。也是一种分治的递归算法
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

经典快速排序

输入存放在数组里，且算法不产生额外的数组

算法步骤

将数组S排序的基本算法：
（1）检查 异常/简单 情形
如果S中元素个数为0或1，则返回
（2）确定枢纽元
取S中任一元素v，称之为枢纽元
（3）数组划分
将S-{v}（s中其余元素）划分为两个不相交的集合：
S={x ∈ S-{v} | x≤v}
S={x ∈ S-{v} | x≥v} （关于x≥v中，是否取等号，在分割策略中讨论）
（4）递归进行S和S的快排

选取枢纽元

错误方法

（1）将第一个元素用作枢纽元。
（2）选取前两个互异的关键词中的较大者作为枢纽元。
如果输入随机，还可以接受，但是如果输入是预排序或是反序的，则会产生一个劣质的分割。（花费时间是二次的，但是实际上没做事）

安全做法

随机选取枢纽元

三数中值分割法

枢纽元最好的选择是数组的中值。（很难算出且耗费资源）
这样的中值的估计量可以通过随机选取三个元素并使用他们的中值作为枢纽元
实际做法：随机性并没有什么用，一般选取左端、右端和中心位置上的三个元素的中值作为枢纽元
意义：消除了预排序输入的坏情形

分割策略

（1）枢纽元与最后的元素交换，使得枢纽元离开要被分割的数据段
（2）双指针，i—>从第一个元素开始 j—>从倒数第二个元素开始。
当 i 在 j 的左边时，将 i 右移，移过小于枢纽元的小元素；将 j 左移，移过大于枢纽元的大元素。
当 i 和 j 停止时，i 指向一个大元素而 j 指向一个小元素。如果 i 在 j 的左边，那么将这两个元素交换。
（3）重复上述过程，直到 i 和 j 彼此交错为止。
（4）将枢纽元与 i 所指向的元素交换

如何处理等于枢纽元的元素

问题描述：当 i 和 j 遇到一个等于枢纽元的元素是否应该停止
答案：进行不必要的交换建立两个均衡的子数组比蛮干冒险得到两个不均衡的子数组好。因此，如果 i 和 j 遇到等于枢纽元的关键字，应该让 i 和 j 都停止。（这是四种可能性中唯一的不花费二次时间的可能）
（1）直观上讲，i 和 j 的动作应该相同，否则分割会出现偏向一方的倾向。
（2）i 和 j 都停止：如果元素均相同，将会产生相等元素间的多次交换，但是会使 i 和 j 在中间交错。
（3）i 和 j 都不停止：需要有相应的程序防止 i 、j 越过数组的端点。因为最后需要把枢纽元交换到 i 最后到过的位置，所以如果数组元素都相同时，会产生非常不均衡的子数组（因为实现时先进行了 i 的while循环），运行时间为O(N)

小数组

小数组不适用递归的快速排序，转为使用插入排序等对小数组有效的排序算法
一种好的截取范围（cutoff range）为 N = 10

算法分析

快速排序也是递归的，仍然也有一个递推公式


其中是S中元素的个数。

最坏情况分析

枢纽元始终是最小元素

最好情况分析

枢纽元正好位于中间，假设两个子数组恰好为原数组的一半大小

平均情况分析

假设每一个大小都是等可能的，因此每个大小均有概率1/N

选择问题的线性期望时间算法

快速选择
与快速排序类似，但是只作一次递归调用而不是两次（参考：机械工业出版社，数据结构与算法分析-java语言描述 P206）

复杂度分析

快速排序的平均时间复杂度也是O(nlogn)。因此，该排序方法被认为是目前最好的一种内部排序方法。
从空间性能上看，尽管快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归。最好的情况下，即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表，所需栈的最大深度为log(n+1)；但最坏的情况下，栈的最大深度为n。这样，快速排序的空间复杂度为O(logn)。

代码实现

package sort;
import java.util.Arrays;
public class QuickSort {
    public static void main(String[] args) {
        //构建测试用例
        //功能测试：随机数组等
        //边界值测试：空数组，只含一个元素的数组等
        //性能测试：正序/倒序等特殊数组
        //异常情况测试：非数组等（有点牵强）
        int[] test={1,7,345,5,3,8,56,1};
        System.out.println(Arrays.toString(quickSort(test,0,test.length-1)));
    }
    //主函数，用来递归进行快速排序
    //start：数组开始元素的下标 end：数组结尾，最后一个元素的下标
    public static int[] quickSort(int arr[],int start,int end) {
        int pivot = arr[median3(arr,start,end)];
        int i = start;
        int j = end;
        while (i<j) {
            while ((i<j)&&(arr[j]>pivot)) {
                j--;
            }
            while ((i<j)&&(arr[i]<pivot)) {
                i++;
            }
            if ((arr[i]==arr[j])&&(i<j)) {
                i++;
            } else {
                swap(arr,i,j);
            }
        }
        if (i-1>start) arr=quickSort(arr,start,i-1);
        if (j+1<end) arr=quickSort(arr,j+1,end);
        return (arr);
    }
    //三分中值分割法确定枢纽元
    public static int median3(int[] array,int left,int right){
        int center = (right-left)/2 + left;
        if(array[left]>array[center]){
            swap(array,left,center);
        }
        if(array[left]>array[right]){
            swap(array,left,right);
        }
        if(array[center]>array[right]){
            swap(array,center,right);
        }
        return center;
    }
    //交换数组内两个元素
    public static void swap(int[] array,int i ,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}