荷兰国旗-不适用于大型数组 [英] Dutch National Flag - Not working for larger array

问题描述

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

My below Dutch National Flag solution doesn't seem to work for the given input array containing only 3 elements - 0, 1 and 2.

如果我减少了数组的大小，它可以工作。我无法识别错误。

If I reduced the size of array, it works. I'm not able to identify the error.

我错过了什么吗？

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

UPDATE : Above same code works for smaller size array : http://ideone.com/bgEgCs

推荐答案

错误是当 arr时，枢轴不得增加[枢轴] ==高。

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

这篇关于荷兰国旗-不适用于大型数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！