荷兰国旗问题（C语言）

荷兰国旗问题

• 简化版荷兰国旗问题

给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)。

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void process(int *a[], int num)
{
    int i = 0;
    int p1 = -1;
    while (i < 8)
    {
        if (a[i] <= num)
        {
            swap(&a[i], &a[p1 + 1]);
            i++;
            p1++;
        }
        else
            i++;
    }
}

int main()
{
    int a[8] = {3, 5, 6, 7, 4, 3, 5, 8};
    int num = 5;
    process(&a, num);

    for (int i = 0; i < 8; i++)
        printf("%d", a[i]);

    return 0;
}

这里举的例子是3,5,6,7,4,3,5,8

左	中	右
<=num	>num	待定

这相当一个一个从左到右的推进。p1指向左，i指向待定区域的开始，然后i向右推进，碰到>num的不做处理，i++,如果碰到<=num的，将i指向的这个符合条件的元素和最靠近左区域的数，也就是中区域最左边的数交换，这样中区域最左边的数就符合<=num，然后i++，p++。

本质是左区域推着中区域向右，最终判断完所有的待定区域。

• 真荷兰国旗问题

给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边，要求额外空间复杂度O(1)，时间复杂度O(N)。

#include 

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void process(int *a[], int flag)
{
    int i = 0;
    int p1 = -1;
    int p2 = 10;//这里直接赋了一个具体的数，本来用sizeof（a）来求，却有bug
    while (i < p2)//注意sizeof(a)在这里得到的并不是一个数组的长度，而是一个元素的长度。
    {
        if (a[i] < flag)
        {
            swap(&a[i], &a[p1 + 1]);
            p1++;
            i++;
        }
        else if (a[i] == flag)
        {
            i++;
        }
        else
        {
            swap(&a[i], &a[p2 - 1]);
            p2--;
        }
    }
}

int main()
{
    int a[10] = {3, 5, 6, 3, 4, 5, 2, 6, 9, 0};
    int flag = 5;
    process(&a, flag);
    for (int i = 0; i < 10; i++)
    {
        printf("%d,", a[i]);
    }

    return 0;
}

<	=	待定	>
p1		i	p2

真正的荷兰国旗问题，多了右边向左的推进，同时注意，i只向右推进，因为i左边的数都被遍历过，所以对于num再交换数之后，不能有i++，因为此时i指向的数是右边交换过来的新数，没有经过遍历，所以i不动。

荷兰国旗问题中的i变化，根据不同情况将数变动至num区域的思想能跟很好地契合进快排算法中去，具体内容见下一篇博客。

感谢你能看到这里，祝好。