QuickSort

快排没啥好讲的，主要是看到剑指offer上说求第K大个数，能达到时间O(N),表示不理解。
同时，以下代码中partition的返回值是每次分组排序得到的一个正确的最终坐标

public class Partition {
// 方便得到每次partition的一个位置，可能在做“寻找特定位置的值”问题上能够优化
    public int partition(int[] array,int start, int end){
        int i = (int)Math.random()*(end-start);
        i += start;
        
        swap(array, i, end);
//small是一个坐标，始终代表的是比那个对比值小并且右边一定是比对比值大的数的位置坐标。因此最终for之后++small,是将对比值放入它在排序中的最终位置,对比值左边全是比它小的，右边全是比它大的
        int small = start - 1; 
        for (int index = start; index < end; index++) {
            if (array[index] < array[end]) {
                ++small;
//一旦small，index不同步向前，说明++small此时指向的数比那个对比值大，然后调换位置
                if (small != index) {
                    swap(array, small, index);
                }
            }
        }
        ++small;
        swap(array, small, end);
        return small;
    }
    
    public void swap(int[] array, int head, int trail) {
        if(head >= 0 && trail < array.length){
            int tmp = array[trail];
            array[trail] = array[head];
            array[head] = tmp;
        }
        return;
    }
    
    public void quickSort(int[] array, int start, int end){
        if (start == end) {
            return;
        }
        int mid = partition(array, start, end);
        
//      无论mid是什么都要分别执行左右两边的子问题，所以不能用else
        if (mid > start) {
            quickSort(array, start, mid-1);
        }
        if (mid < end) {
            quickSort(array, mid+1, end);
        }
    }
    
    public static void main(String[] args) {
        int[] array = {3,0,1,2,5,6};
        
        Partition partition = new Partition();
        
        partition.quickSort(array, 0, 5);
        
// 亲测有效
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
}