算法 - 快速排序 - 荷兰国旗问题

问题一

给定一个数组 arr，和一个数 num，请把小于等于 num 的数放在数组的左边，大于 num 的数放在数组的右边。

要求额外空间复杂度O(1)，时间复杂度O(N)。

思路：遇到 arr[i] 小于等于 number 的数，交换 index + 1 和 arr[i]，此时 index + 1 位置的数变成小于等于 number，index++；遇到 arr[i] 大于 number 的数，不做任何处理。index 表示的是数组中小于等于 number 的区域。

<= number
    swap(arr, index+1, i)
    index++
>
    donothing

public static void main(String[] args) {
    int[] arr = {1, 4, 56, 23, 34, 6, 34, 76, 23};
    int number = 30;
    fun1(arr, number);
    System.out.println(Arrays.toString(arr));
}

public static void fun1(int[] arr, int number) {
    int index = -1;
    for (int i = 0; i < arr.length; i++) {
        //当扫描的数是小于等于 number，小于等于区域 index++
        if (arr[i] <= number) {
            swap(arr, index + 1, i);
            index++;
        }
    }
}

public static void swap(int[] arr, int first, int second) {
    int temp = arr[first];
    arr[first] = arr[second];
    arr[second] = temp;
}

output: [1, 4, 23, 6, 23, 56, 34, 76, 34]

输出的数组分成两个部分，小于等于 30 和大于 30 的。

问题二：荷兰国旗问题

给定一个数组 arr，和一个数 num，请把小于 num 的数放在数组的左边，等于 num 的数放在数组的中间，大于 num 的数放在数组的右边。

要求额外空间复杂度O(1)，时间复杂度O(N)。

思路：cur 为遍历的当前数指针，less 表示数组划分的小于 num 的区域，more 表示数组划分的大于 num 的区域。当 arr[cur] < num 时，交换 less + 1 和 cur 位置的数，此时 less + 1 位置的数小于 num，less + 1；当 arr[cur] = num 时，cur + 1；当 arr[cur] > num 时，交换 cur 和 more - 1 位置的数，more 区域从 [more, end] 扩大到 [more - 1, end]，此时 cur 位置的数交换而来，大小仍需计算，故 cur 不变。

 while (cur != more && cur < arr.length) {
    < number
        swap(arr,less+1, cur)
        less++
        cur++
    = number
        cur++
    > number
        swap(arr, more-1, cur)
        more--
        //此处 cur 不变，仍需要看交换过来的 more-1 位的大小
}

public static void main(String[] args) {
    int[] arr = {1, 4, 65, 50, 3, 4, 1, 50, 3, 64, 6, 64, 50, 3};
    fun1(arr, 50);
    //output: [1, 4, 3, 3, 4, 1, 3, 6, 50, 50, 50, 64, 64, 65]
    //由 number = 50 分为三个区域，小于 50，等于 50，大于 50
    System.out.println(Arrays.toString(arr));
}

public static void fun1(int[] arr, int number) {
    if (arr == null || arr.length < 2) return;
    int less = -1;
    int more = arr.length;
    int cur = 0;
    while (cur != more) {
        if (arr[cur] < number) {
            swap(arr, less + 1, cur);
            less++;
            cur++;
        } else if (arr[cur] == number) {
            cur++;
        } else {
            swap(arr, more - 1, cur);
            more--;
        }
    }
}

public static void swap(int[] arr, int first, int second) {
    int temp = arr[first];
    arr[first] = arr[second];
    arr[second] = temp;
}

output: [1, 4, 3, 3, 4, 1, 3, 6, 50, 50, 50, 64, 64, 65]

由 number = 50 分为三个区域，小于 50，等于 50，大于 50。

总结

问题一和问题二的算法思路是层层递进的，与快排中的单边循环法也有前后关系。在单向遍历过程中，利用多个指针将数组内部划分成不同的区域。