快速排序

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

JAVA代码实现

public class quickSort {
    public static void quick(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        quick(arr,0,arr.length-1);
    }

    private static void quick(int[] arr, int l, int r) {
        if (l < r){
            swap(arr,l+(int)(Math.random() * ( r - l + 1)),r);
            int[] p = partition(arr,l,r);
            quick(arr,l,p[0]-1);
            quick(arr,p[1]+1,r);
        }
    }

    private static int[] partition(int[] arr, int l, int r) {
        /*
        把数组分成三部分
        1. 把比选中的小的数字放左边
        2. 相等的放中间
        3. 比选中大的数字放右边
        */
        int less = l-1;
        int more = r;
        while(l < more){
            if (arr[l] < arr[r]){
                swap(arr,++less,l++);
            }else if(arr[l] > arr[r]){
                swap(arr,--more,l);
            }else {
                l++;
            }
        }
        swap(arr,more,r);
        return new int[] {less+1,more};
    }

    private static void swap(int[] arr, int i, int r) {
        int tmp = arr[i];
        arr[i] = arr[r];
        arr[r] = tmp;
    }
}