快速排序

选择一个基准数(任意)
交换位置, 直到基准数的左边都比基准数小, 基准数的右边都比基准数大
这样就将一个数组分为了基准数左数组和右数组
再次从头执行操作(递归)

第二步具体怎么实现呢?

在数组首尾设置两个指针i、j，向数组中间遍历，每次与基准数比较，若i遇到了比基准数更大的值，停下；j遇到了比基准数更小的值，停下；交换i与j位置的值；直到i与j相遇，再将基准数交换到i或j所在的位置，此时，数组中基准数左边都比基准数小，而右边都比基准数大了。

代码：

@Override
public void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

private void quickSort(int[] arr, int low, int high) {
    if (low >= high) return;
    // 将第一位做基准数, 使base左边都比base小, base右边都比base大
    int base = arr[low], i = low, j = high;
    while (i < j) {
        while (arr[j] >= base && i < j) j--;
        while (arr[i] <= base && i < j) i++;
        if (i < j) swap(arr, i, j);
    }
    // 交换基准数到中间
    swap(arr, low, i);
    // 递归左右数组
    quickSort(arr, low, i - 1);
    quickSort(arr, i + 1, high);
}

public void swap(int[] arr, int i, int j) {
    if (i == j) return;
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

测试#

/**
 * 生成一个范围在[min, max]的随机数组
 *
 * @param length 数组长度
 * @param min    数组中最小值
 * @param max    最大值
 * @return 随机数组
 */
public int[] generateRandomArray(int length, int min, int max) {
    if (max - min < 1 || length < 1) {
        throw new IllegalArgumentException("参数异常");
    }
    int[] array = new int[length];
    double random;
    for (int i = 0; i < length; i++) {
        // 范围 [min, max+1)
        random = Math.random() * (max + 1 - min) + min;
        array[i] = (int) random;
    }
    return array;
}

/**
 * 判断arr数组是否有序
 *
 * @param arr
 * @return
 */
public boolean isRightSort(int[] arr) {
    int[] arrCopy = Arrays.copyOf(arr, arr.length);
    Arrays.sort(arrCopy);
    return Arrays.equals(arrCopy, arr);
}

/**
 * 与java自带的排序方法作比较, 测试排序方法的正确性
 *
 * @param testTimes  测试次数
 * @param sortMethod 待测试的排序方法
 */
public void testSortMethod(int testTimes, Consumer<int[]> sortMethod) {
    for (int i = 0; i < testTimes; i++) {
        int[] arr = generateRandomArray(10,-100,100);
        sortMethod.accept(arr);
        if (!isRightSort(arr)) {
            System.out.println("第" + (i + 1) + "次排序出问题啦!!!");
            System.out.println("sortMethod 排序结果: " + Arrays.toString(arr));
            return;
        }
    }
    System.out.println("通过" + testTimes + "次测试, 哎哟不错哦");
}