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

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

作者：Grey

原文地址：

博客园：荷兰国旗问题与快速排序算法

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

荷兰国旗问题

问题描述

给定一个整数数组，给定一个值 K，这个值在原数组中一定存在，要求把数组中小于 K 的元素放到数组的左边，大于K的元素放到数组的右边，等于 K 的元素放到数组的中间。

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

主要思路

设置两个变量l和r，其中小于i位置的值都是比 K 小的数，$i\dots 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\dots R]$范围上，进行快速排序的过程如下

1. 在这个范围上，随机选一个数记为num，

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

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

4. 对$arr[b+\mathrm{1...}R]$进行快速排序(递归)

因为每一次荷兰国旗算法都会搞定一批数的位置且不会再变动，所以排序能完成

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

2. 随机选一个数进行划分的目的就是让好情况和差情况都变成概率事件

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

4. 那么所有情况都考虑，时间复杂度就是这种概率模型下的长期期望。

时间复杂度$O(N\ast logN)$，额外空间复杂度$O(logN)$都是这么来的。

题目链接：LintCode 464 · Sort Integers II

完整代码见

public class Solution {

    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};
    }
}

更多

算法和数据结构学习笔记

算法和数据结构学习代码