大牛们的问题做不来， 也就自娱自乐的看一些简单的小问题哈， 拿来分享一下

不是什么复杂的问题，

是一个排列0，1， 2 的问题， 好像和德国国旗问题什么的怪像的( Dutch national flag problem.)

也就是给定一个数组 {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};

 然后排好队就行了， {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}


直接给程序太生硬，给个连接吧，里面有解释

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

因为感觉只是要排列三种数，所以没那么复杂了

Time Complexity: O(n)

程序代码：

#include <stdio.h>

void swap(int *a, int *b);

void sort012(int a[], int arr_size) {

    int lo = 0;
    
    int hi = arr_size - 1;

    int mid = 0;

    while( mid <= hi ) {

        switch ( a[mid] ) {
            
            case 0:
                swap ( &a[lo++], &a[mid++] );
                break;

            case 1:
                mid++;
                break;

            case 2:
                swap ( &a[mid], &a[hi--]);
                break;
        }
    }
}

void swap(int *a, int *b) {

    int temp = *a;

    *a = *b;

    *b = temp;
}

void printArray(int arr[], int arr_size) {

    int i;

    for( i = 0; i < arr_size; i++)

        printf("%d ", arr[i] );
    
    printf("\n");
}

int main(void) {

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

    int arr_size = sizeof( arr ) / sizeof( arr[0] );
    
    int i;
    
    sort012( arr, arr_size );

    printf("array after segregation ");

    printArray( arr, arr_size );

    return 0;
}

[ 本帖最后由 madfrogme 于 2012-8-21 12:29 编辑 ]

Time Complexity: O(n) :)

杨大哥的意思是算出012各有几个，输出一下就可以了？

那就当它是一个排列的小技巧吧，我也是一点一点来了

不过给出的排列如果是规则的，就有一些多余的比较了

{0, 0, 0, 1, 1, 2, 2, 2, 2}

感觉可以把标识最高位的 hi 放到 最后那个 1 的地方，而不是 最后那个 2

[ 本帖最后由 madfrogme 于 2012-8-21 14:26 编辑 ]