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

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

荷兰国旗问题

给定一个整数数组，给定一个值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]有三种情况

arr[i] > K

arr[i] == K

arr[i] < K

i位置的值和r - 1位置的值交换，然后r--，i++；

i位置的值和l + 1位置的值交换，然后l++，i++；

i位置的值和r-1位置的值交换，然后i++。

题目链接：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]范围上，进行快速排序的过程如下

随机选一个数记为num，

num对该范围使用荷兰国旗算法，< num 的数在左部分，== num 的数中间，> num 的数在右部分。假设== num的数所在范围是[a,b]

arr[L..a-1]进行快速排序(递归

arr[b+1..R]进行快速排序(递归

1）通过分析知道，划分值越靠近中间，性能越好；越靠近两边，性能越差

3）把每一种情况都列出来，会有每种情况下的时间复杂度，但概率都是1/N

时间复杂度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};
    }
}