荷蘭國旗問題：設有一個僅由紅、白、藍3種顏色的條塊組成的條塊序列。請編寫一個時間復雜度為O(n)的算法，使得這些條塊按紅、白、藍的順序排好，即排成荷蘭國旗圖案。

算法設計

利用鏈式基數排序，將紅、白、藍3種顏色分配到3個鏈表上，然后對鏈表進行收集。

具體實現

typedef enum{Red,White,Blue}Color; typedef struct ListNode{Color color;struct ListNode *next; }Node,*LinkList; void FlagAdjust(Color a[],int n) // 將三種顏色組成的序列重排為按照紅、白、藍的順序排列 {LinkList list[3]; //創建3個鏈表，分別儲存紅、白、藍色 int count = 0;for(int i=0; i<3; i++){ list[i] = (Node*)malloc(sizeof(Node));list[i]->next = NULL; //頭結點指針域指向NULL }for(int i=0; i<n; i++){ if(a[i]==Red){Node *p = (Node*)malloc(sizeof(Node));p->color = Red;p->next = list[Red]->next;list[Red]->next = p;} else if(a[i]==White){Node *p = (Node*)malloc(sizeof(Node));p->color = White;p->next = list[White]->next;list[White]->next = p;} else{Node *p = (Node*)malloc(sizeof(Node));p->color = Blue;p->next = list[Blue]->next;list[Blue]->next = p;}} //分配 Node *q = list[Red]->next;while(q!=NULL){a[count] = q->color;count++;q = q->next;}q = list[White]->next;while(q!=NULL){a[count] = q->color;count++;q = q->next; }q = list[Blue]->next;while(q!=NULL){a[count] = q->color;count++;q = q->next;} //收集 }

總結

以上是生活随笔為你收集整理的荷兰国旗问题（利用基数排序思想实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

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