快速排序

分类 ------------ 内部比较排序
数据结构 --------- 数组
最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
平均时间复杂度 ---- O(nlogn)
所需辅助空间 ------ O(logn)～O(n),主要是递归造成的栈空间的使用(用来保存left和right等局部变量),取决于递归树的深度一般为O(logn),最差为O(n)（基本有序的情况）
稳定性 ---------- 不稳定

原理

       快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。

步骤

1. 从序列中挑出一个元素，作为"基准"(pivot).
2. 把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区(partition)操作。
3. 对每个分区递归地进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。

代码实现

public class QuickSort {
    // 划分函数
    int partition(Integer a[], int left, int right)
    {
        // 选择最后一个元素作为基准
        int pivot = a[right];
        // tail为小于基准的子数组最后一个元素的索引
        int tail = left - 1;
        // 遍历基准以外的其他元素
        for (int i = left; i < right; i++)
        {
            // 把小于等于基准的元素放到前一个子数组中
            if (a[i] <= pivot)
            {
                tail++;
                Tool.exchange(a, tail, i);
            }
        }
        // 最后把基准放到前一个子数组的后边,剩下的子数组既是大于基准的子数组
        Tool.exchange(a, tail + 1, right);
        // 该操作很有可能把后面元素的稳定性打乱,所以快速排序是不稳定的排序算法,最终返回基准的索引
        return tail + 1;
    }

    void quicksort(Integer a[], int left, int right)
    {
        // 基准的索引
        int pivot_index;
        if (left < right)
        {
            pivot_index = partition(a, left, right);
            quicksort(a, left, pivot_index-1);
            quicksort(a, pivot_index+1, right);
        }
    }

    public static void main(String[] args){
        Integer[] a = {3,4,1,9,5,2,6,10,20,16,13,11,0};
        QuickSort sort = new QuickSort();
        sort.quicksort(a,0,a.length-1);
        System.out.println("array by QuickSort is " + Tool.arrayToString(a));

    }
}

public class Tool {
    public static <T> String arrayToString(T[] array){
        StringBuilder builder = new StringBuilder("[");
        for (int i = 0; i < array.length; i++){
            T item = array[i];
            builder.append(item + "");
            if (i != array.length - 1){
                builder.append(",");
            }
        }

        builder.append("]");
        return builder.toString();
    }

    public static <T> void exchange(T[] array, int i, int j){
        T temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

实现结果：

array by QuickSort is [0,1,2,3,4,5,6,9,10,11,13,16,20]