快速排序

找到分界点：

public static void sort(Comparable[] arr) {
    int n = arr.length;
    sort(arr, 0, n - 1);
}

private static void sort(Comparable[] arr, int l, int r) {
    if (l >= r) {
        return;
    }
    int p = partition(arr, l, r);
    sort(arr, l, p - 1);
    sort(arr, p + 1, r);
}

private static int partition(Comparable[] arr, int l, int r) {
    Comparable v = arr[l];
    int j = l;
    for (int i = l + 1; i <= r; i++) {
        if (arr[i].compareTo(v) < 0) {
            j++;
            swap(arr, j, i);
        }
    }
    swap(arr, l, j);
    return j;
}

private static void swap(Object[] arr, int i, int j) {
    Object t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

高级排序在需要排列的数据量很小的时候，可以用插入排序优化

存在的问题： 当测试用例为近乎有序的数组时，以上排序方法会退化为n^2的算法，结果无法接受。优化办法是：在patition方法内选择分界元素时，不要指定arr[l]，而是采用随机的方式得到，这样从概率的角度可以论证，复杂度为O(nlogn)。

需要继续优化partition方法(双路快排)

// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p];
private static int partition(Comparable[] arr, int l, int r){
    // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
    swap( arr, l , (int)(Math.random()*(r-l+1))+l );
    Comparable v = arr[l];
    // arr[l+1...i) <= v; arr(j...r] >= v
    int i = l+1, j = r;
    while( true ){
        // 注意这里的边界, arr[i].compareTo(v) < 0, 不能是arr[i].compareTo(v) <= 0
        while( i <= r && arr[i].compareTo(v) < 0 )
            i ++;

        // 注意这里的边界, arr[j].compareTo(v) > 0, 不能是arr[j].compareTo(v) >= 0
        while( j >= l+1 && arr[j].compareTo(v) > 0 )
            j --;

        if( i > j )
            break;

        swap( arr, i, j );
        i ++;
        j --;
    }
    swap(arr, l, j);
    return j;
}