快速排序

经典快排：取数组中最后一个位置的数，小于等于这个数的放左区域，大于这个数的放右区域。
改进的随机快排：随机从数组中取一个数与最后一个位置的数进行交换，再以最后一个位置的数为中心划分，小于这个数的放小于区域，等于这个数的放等于区域，大于这个数的放大于区域。
两者比较：经典快排与数据状况有很大关系，一次只能排好一个数的准确位置，如果出现多个等于这个数的情况，则在时间复杂度的常量级别上不如改进的随机快排。

改进的随机快排代码实现：

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

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

private static int[] partition(int[] arr,int left,int right) {
    // 小于区域
    int less = left - 1;
    // 大于区域（包含待比较的数right）
    int more = right;
    // 当前数left和大于区域相撞为循环结束条件
    while (left < more) {
        if (arr[left] < arr[right]) {
            // 将小于区域的下一个数与当前数交换后，当前数向右移动1位
            swap(arr,left++,++less);
        } else if (arr[left] > arr[right]) {
            // 将大于区域的前一个数与当前数交换后，大于区域向左扩1位，当前数位置不变
            swap(arr,left,--more);
        } else {
            // 相等则当前数跳下一位
            left++;
        }
    }
    // 将比较的数放回等于区域（开始大于区域包含了比较的数）
    swap(arr,right,more);
    return new int[] {less + 1,more};
}

private static void swap(int[] arr,int x,int y) {
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}