每日一题系列

文章目录

• 荷兰国旗问题（c语言实现）
• 思路一：暴力求解法
• • 代码一（暴力求解）
• ②、思路二：三指针法
• • 下面给出思路二的代码
• // 后记

荷兰国旗问题（c语言实现）

💘简单介绍一个荷兰国旗问题

🏃 这个问题是由荷兰科学家E.W.Dijkstra与1974年提出。
🏃 设有排成一排的N个桶，每个桶里装有红、白、蓝三个颜色之一的一个小石子。
🏃 要求将这些小石子排列，使红在前，白在中间，蓝色的在后面。
🏃 重排时，要求每个小石子的颜色只能查看一次，而且只允许两两交换的方法来调整小石子的位置。

💘用数组和0、1、2来通俗的解释一下：

（重排之前）数组 = 1 2 0 1 1 2 0 0 0 2 1 1
（重排之后）数组 = 0 0 0 0 1 1 1 1 1 2 2 2

思路一：暴力求解法

🏃 遍历一遍数组，然后统计出数组中0 1 2的个数，然后重新将0 1 2 输入。

这种方法虽然能解决问题，但是与题目的要求不符，因为题目要求只能用两两交换的方法。
但我还是给出代码，方便大家参考和对比第二种思路。

代码一（暴力求解）

void SortColour(int arr[10]){int red= 0;//红色个数（0）int white = 0;//白色个数（1）int i = 0;//遍历数组，统计红白的个数//为什么不记录蓝色的数目呢？//因为红白的个数知道以后，蓝色的自然就知道了for (i = 0; i < 10; i++){//统计红色个数if (arr[i] == 0){red++;}//统计白色个数else if (arr[i] == 1){white++;}}//按照红白蓝的个数以此修改原数组//红色 0 ~ red-1//白色 red~ red+ white - 1//蓝色 red+ white ~ 最后for (i = 0; i < red; i++){arr[i] = 0;//红色位置}for (i = red; i < red + white ; i++){arr[i] = 1;//白色位置}for (i = red + white ; i < 10; i++){arr[i] = 2;//蓝色位置}}//这里定义一个打印数组的函数，方便循环使用void print(int arr[10]){int i = 0;for (i = 0; i < 10; i++){printf("%d ", arr[i]);}printf("\n");}int main(){int arr[10] = { 1,0,2,2,1,0,1,0,1,2 };printf("重排前->");print(arr);SortColour(arr);printf("重后->");print(arr);return 0;}

输出结果如下：

💘上述暴力求解思路没有压力，实现起来也不是很复杂，唯一需要注意的一点就是最后重新录入0 1 2时，注意好数组下标的位置即可。

②、思路二：三指针法

🏃 定义三个指针 pred next pblue（其实是数组下标，形象一点当做指针）
🏃 pr 初始值为0，用来指向红色的最右边元素的下一个元素（即是红色区域的边界）
🏃 next 初始值为0，用来扫描数组的每个元素
🏃 pblue初始值为n（元素个数，数组最后一个元素之后的下标），用来指向蓝色区域最左边的元素

💘 初始状态如下：

💘 接下来讲解思路的细节，大家跟上节奏，不要掉队

🏃 next在扫描为止区域时会遇到三种情况

🏃 第一种情况：碰见 0 （即是红色）
🏃 直接与 pred 下标的元素交换
🏃 交换完之后将 pred 的值加 1，next 的值也加1（为什么next的值也要加1呢？看到最后一种情况后，我会解释）

🏃 第二种情况：碰见 1 （即是白色）
🏃 不移动任何元素，next 直接向后移动一位（这样 pred 与 next 之间全部都是数字1（白色））

🏃 第三种情况：碰见 2（即是蓝色）
🏃 与 blue - 1（blue 的前一个元素）交换
🏃 交换完之后，将 blue 的值减 1
🏃 注意，此时 next 不能 +1，因为交换过来的元素不晓得它是什么颜色

🏃 通过若干过程，就可以将数组分割成下图模样：

🏃 到这里就可以解释为什么碰到 0 交换之后 next 的指针也要 +1
🏃 因为经过三种情况的处理，pred 指向的元素一定是 1 或 0 （极端情况，数组里全是0）
🏃 因此交换之后，next 可以顺势往后走一步，避免全是 0 的情况，无法结束循环。

🏃 最后，只需等到 next 与 pblue 相遇，循环就可以终止

下面给出思路二的代码

//打印数组的函数void print(int arr[10]){int i = 0;for (i = 0; i < 10; i++){printf("%d ", arr[i]);}printf("\n");}void SortColour2(int arr[10]){int pred = 0;int next = 0;int pblue = 10;while (next != pblue){if (arr[next] == 0){    //交换两个元素int tmp = arr[pred];arr[pred] = arr[next];arr[next] = tmp;//两个指针同时+1pred++;next++;}else if (arr[next] == 1){//遇到1 next直接继续前进next++;}else{    //当遇到2时，bule 后退一步    //并将指向的元素与next指向的元素交换pblue--;int tmp = arr[pblue];arr[pblue] = arr[next];arr[next] = tmp;}}}int main(){int arr[10] = { 0,2,0,2,1,0,1,0,1,1 };printf("重排前->");print(arr);//SortColour1(arr);SortColour2(arr);printf("重排后->");print(arr);return 0;}

// 后记

🏃以后每天更新一道算法题，并且附带超级详细的讲解和注释，所有代码均可复制到编译器里自测。
🏃如果有疑问的小伙伴，欢迎评论留言，我会详细解答。

// 文章中任何错误都请大佬指正。