3

我下面的荷兰国旗解决方案似乎不适用于仅包含 3 个元素（0、1 和 2）的给定输入数组。

如果我减小数组的大小，它会起作用。我无法识别错误。

我错过了什么吗？

class DNF{

    public static void sort(int [] arr, int size, int low, int high) {

        if(size == 0)
            return;

        int lower = 0;
        int upper = size - 1;

        while(lower < size && arr[lower] == low)
            lower++;

        while(upper >=0 && arr[upper] == high)
            upper--;

        int temp = 0;
        int pivot;
        for(pivot = lower; pivot <= upper; ) {
            if(arr[pivot] == low) {
                temp = arr[pivot];
                arr[pivot] = arr[lower];
                arr[lower] = temp;
                pivot++;
                lower++;
            } else if(arr[pivot] == high) {
                temp = arr[pivot];
                arr[pivot] = arr[upper];
                arr[upper] = temp;
                pivot++;
                upper--;
            } else {
                pivot++;
            }
        }
    }
    public static void main(String [] args) {

        int arr [] = {0,1,2,1,2,0,1,1,1,0,0,0,1,0,2,1};

        for(int i=0; i<arr.length; i++) {
            System.out.print(arr[i]+" "); //0 1 2 1 2 0 1 1 1 0 0 0 1 0 2 1 
        }

        sort(arr, arr.length, 0, 2);
        System.out.println();

        for(int i=0; i<arr.length; i++) {
            System.out.print(arr[i]+" "); // 0 0 0 0 0 0 1 1 1 1 1 2 1 1 2 2 
        }
    }
}

更新：上面相同的代码适用于较小的数组：http: //ideone.com/bgEgCs

4

2 回答 2

2

错误是当arr[pivot] == high.

是的，我作弊了：http ://en.wikipedia.org/wiki/Dutch_national_flag_problem

于 2013-07-17T18:08:26.763 回答
1

当您处于 arr[pivot] == high 时，您不应该移动您的轴心点，您正在切换的值可能不是您想要切换的低值。您只知道鞋面现在处于正确位置

} else if (inArray[pivot] == high) {
    temp = inArray[pivot];
    inArray[pivot] = inArray[upper];
    inArray[upper] = temp;
    pivot++; //This line is not needed
    upper--;
于 2013-07-17T18:10:08.633 回答