荷蘭國旗問題

• 簡化版荷蘭國旗問題

給定一個數組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++;}elsei++;} }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 <stdio.h>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）來求，卻有bugwhile (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++，而>num再交換數之后，不能有i++，因為此時i指向的數是右邊交換過來的新數，沒有經過遍歷，所以i不動。

荷蘭國旗問題中的i變化，根據不同情況將數變動至<num和>num區域的思想能跟很好地契合進快排算法中去，具體內容見下一篇博客。

感謝你能看到這里，祝好。

總結

以上是生活随笔為你收集整理的荷兰国旗问题（C语言）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。