快速排序

实现思路

1. 荷兰国旗：小于目标数字在左边，大于目标数字在右边

2. 荷兰国旗扩展：小于目标数字在左边，等于目标数字在中间，大于目标数字在右边

   • 左指针向右移动，遇到大于目标数的将右指针所指数字与当前数字交换，右指针往左移一位，左指针不动，继续比较

   • 止步于左右指针相遇

3. 荷兰国旗是将最后一个数字作位中间数，快排防止出现本就有序的数组排序导致出现复杂度过高的情况，先随机选取数组中的一个数字作为目标数字并与最后一位交换

4. 利用荷兰国旗的方式首次将数组处理为左（小于目标数）中（等于目标数）右（大于目标数）

5. 重新将处理后的数组分组，递归处理

TALK IS CHEAP

/**
* 荷兰国旗：小于等于目标数字在左边，大于在右边
*/
@Test
public void heLanQi() {

    int[] arr = {1, 3, 3, 5, 6, 7, 8, 4, 5, 2, 5};
    // 目标数字 5
    int target = 5;
    // 左边边界
    int left = -1;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] <= target) {
            left++;
            if (i != left) {
                arr[i] = arr[i] ^ arr[left];
                arr[left] = arr[i] ^ arr[left];
                arr[i] = arr[i] ^ arr[left];
            }
        }
    }
    System.out.println(Arrays.toString(arr));

}

/**
* 荷兰国旗扩展：小于目标数字在左边，等于目标数字在中间，大于目标数字在右边
*/
@Test
public void heLanQiExtend() {
    int[] arr = {1, 3, 3, 5, 6, 7, 8, 4, 5, 2, 5};
    // 左边界
    int left = -1;
    // 有边界
    int right = arr.length;
    // 目标数字
    int target = 5;
    for (int i = 0; i < arr.length; i++) {
        if (i == right) {
            break;
        }
        if (arr[i] < target) {
            left++;
            if (i > left) {
                arr[i] = arr[i] ^ arr[left];
                arr[left] = arr[i] ^ arr[left];
                arr[i] = arr[i] ^ arr[left];
            }
        }
        if (arr[i] > target && i < right) {
            right--;

            arr[i] = arr[i] ^ arr[right];
            arr[right] = arr[i] ^ arr[right];
            arr[i] = arr[i] ^ arr[right];
            i--;
        }

    }
    System.out.println(Arrays.toString(arr));
}

/**
* 快速排序
*/
@Test
public void quickSortTest() {
    int[] arr = {1, 3, 3, 5, 6, 7, 8, 4, 5, 2, 5};
    quickSort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
}

/**
* 快速排序
*
* @param arr 被排序数组
* @param l 此处为数组最左侧坐标
* @param r 此处为数组最右侧坐标
*/
private void quickSort(int[] arr, int l, int r) {
    if (arr == null || arr.length < 2) return;
    if (l < r) {
        // 1.随机找到一个数字，并将其与最后一位更换位置
        swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
        // 2.得到小于随机数的左边界与大于随机数的右边界，并将小于的数字都放置在左边界内，大于的数字都放置在有边界外
        int[] p = partition(arr, l, r);
        // 3.递归分区左边和右边的数据
        quickSort(arr, l, p[0]);
        quickSort(arr, p[1], r);
    }
}

private int[] partition(int[] arr, int l, int r) {
    // 左边界位置
    int less = l - 1;
    // 有边界位置
    int more = r;
    while (l < more) {
        if (arr[l] < arr[r]) {
            less++;
            if (l > less) {
                swap(arr, less, l++);
            } else {
                l++;
            }
        } else if (arr[l] > arr[r]) {
            more--;
            if (l < more) {
                swap(arr, more, l);
            }
        } else {
            l++;
        }
    }
    // 将最后一个上次随机的数字与有边界的数字交换，因为随机的数字第一次被换到最右边了，交换完成后应该将随机的数字放置中间区域
    swap(arr, more, r);
    // 上个交换将最后一位换回中间位置，因此more位置需向右移动
    return new int[]{less, more + 1};
}

private void swap(int[] arr, int l, int r) {
    int temp = arr[l];
    arr[l] = arr[r];
    arr[r] = temp;
}