5.荷兰旗问题(Rainbow sort)

题目

5.png

给定一个数组{-1,1,0,-1,0,1} 数组中只有确定的3种重复元素-1,0,1，设计一个算法将其排列成{-1,-1,0,0,1,1}。

解题思路

这种荷兰期问题的核心解法很简单:ijk,ijk,ijk重要的事情说三次，为什么是ijk呢，因为解这种问题需要定义3个指针配合运算，
[0,i)i左边的元素都是-1,
[i,j)中间的元素都是0,
(k, arr.length-1] k右边的元素的都是1,
比较简单就不多做分析了，直接上代码。

Code

public class RainbowSortTest {

    @Test
    public void test() throws Exception {
        int[] arr = new int[]{1, -1, 0, 1, -1, 0};
        rainbowSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public int[] rainbowSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return arr;
        }
        int i = 0, j = 0, k = arr.length - 1;
        while (j <= k) {
            if (arr[j] == -1) {
                swap2(arr, i, j);
                i++;
                j++;
            } else if (arr[j] == 0) {
                j++;
            } else if (arr[j] == 1) {
                swap2(arr, j, k);
                k--;
            }
        }
        return arr;
    }

    //交换数组的元素 实现2，在函数调用次数巨大的情况下可以提高一些效率
    private void swap2(int[] arr, int index1, int index2) {
        if (index1 == index2) return;
        arr[index1] = arr[index1] + arr[index2];
        arr[index2] = arr[index1] - arr[index2];
        arr[index1] = arr[index1] - arr[index2];
    }
    //交换数组的元素
    private void swap1(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

时空复杂度

一个循环无嵌套，时间复杂度O(n)，没有使用多余的数组或递归空间复杂度O(1).