荷蘭國旗問題與快速排序演演算法

作者：Grey

原文地址：

部落格園：荷蘭國旗問題與快速排序演演算法

CSDN：荷蘭國旗問題與快速排序演演算法

荷蘭國旗問題

問題描述

給定一個整數陣列，給定一個值K，這個值在原陣列中一定存在，要求把陣列中小於K的元素放到陣列的左邊，大於K的元素放到陣列的右邊，等於K的元素放到陣列的中間。

時間複雜度要求O(N)，空間複雜度要求O(1)。

主要思路

設定兩個變數l和r，其中<i位置的值都是比 K 小的數，i……r都是等於 K 的數，>r都是大於 K 的數。

初始值l = - 1， r = arr.length; 表示都還沒考察過陣列的任何一個元素，然後開始遍歷陣列，遍歷到的位置為i,arr[i]有三種情況

情況 1

arr[i] > K

情況 2

arr[i] == K

情況 3

arr[i] < K

對於情況 1，只需要將i位置的值和r - 1位置的值交換，然後r--，i++；

對於情況 3，只需要將i位置的值和l + 1位置的值交換，然後l++，i++；

對於情況 2，只需要將i位置的值和r-1位置的值交換，然後i++。

陣列遍歷完畢後，原始陣列就形成了：小於K的元素放到陣列的左邊，大於K的元素放到陣列的右邊，等於K的元素放到陣列的中間。

題目連結：LeetCode 75. Sort Colors

完整程式碼見

class Solution {
    public static void sortColors(int[] arr) {
        int l = -1;
        int r = arr.length;
        int i = 0;
        while (i < r) {
            if (arr[i] > 1) {
                swap(arr, i, --r);
            } else if (arr[i] < 1) {
                swap(arr, i++, ++l);
            } else {
                // arr[i] == 1
                i++;
            }
        }
    }

    private static void swap(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        arr[l] = arr[l] ^ arr[r];
        arr[r] = arr[l] ^ arr[r];
        arr[l] = arr[l] ^ arr[r];
    }
}

快速排序

基於上述荷蘭國旗演演算法的原型，我們可以實現快速排序演演算法，流程是

在arr[L……R]範圍上，進行快速排序的過程如下

0）在這個範圍上，隨機選一個數記為num，

1）用num對該範圍使用荷蘭國旗演演算法，< num 的數在左部分，== num 的數中間，> num 的數在右部分。假設== num的數所在範圍是[a,b]

2）對arr[L..a-1]進行快速排序(遞迴)

3）對arr[b+1..R]進行快速排序(遞迴)

因為每一次荷蘭國旗演演算法都會搞定一批數的位置且不會再變動，所以排序能完成

1）通過分析知道，劃分值越靠近中間，效能越好；越靠近兩邊，效能越差

2）隨機選一個數進行劃分的目的就是讓好情況和差情況都變成概率事件

3）把每一種情況都列出來，會有每種情況下的時間複雜度，但概率都是1/N

4）那麼所有情況都考慮，時間複雜度就是這種概率模型下的長期期望！

時間複雜度O(N*logN)，額外空間複雜度O(logN)都是這麼來的。

題目連結：LintCode 464 · Sort Integers II

完整程式碼見

public class Solution {
    /**
     * @param a: an integer array
     * @return: nothing
     */
    public static void sortIntegers2(int[] arr) {
        if (null == arr || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    public static void process(int[] arr, int s, int e) {
        if (s >= e) {
            return;
        }
        swap(arr, e, s + (int) (Math.random() * (e - s)));
        int[] range = sortColors(arr, s, e);
        process(arr, s, range[0] - 1);
        process(arr, range[1] + 1, e);
    }

    public static 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];
    }

    public static int[] sortColors(int[] arr, int s, int e) {
        int l = s - 1;
        int r = e + 1;
        int p = arr[e];
        int i = s;
        while (i < r) {
            if (arr[i] > p) {
                swap(arr, i, --r);
            } else if (arr[i] < p) {
                swap(arr, i++, ++l);
            } else {
                i++;
            }
        }
        return new int[]{l + 1, r - 1};
    }
}

演演算法和資料結構筆記

參考資料

演演算法和資料結構體系班-左程雲

荷蘭國旗問題與快速排序演演算法

荷蘭國旗問題與快速排序演演算法

荷蘭國旗問題

快速排序

更多

參考資料