问题描述
现有红白蓝三个不同颜色的小球,乱序排列在一起,请重新排列这些小球,使得红白蓝三色的同颜色的球在一起. 之所以被称为荷兰国旗问题, 是因为荷兰国旗正好有红白蓝三种颜色构成, 将红白蓝三色小球想象成条状物,有序排列后正好组成荷兰国旗.
问题分析
荷兰国旗问题其实是一个数组排序问题, 可以将红白蓝三种颜色分别用数字0,1,2表示, 然后对数组中的数值进行排序.
问题解决
思路一
- 遍历数组, 统计红白蓝三色球(0,1,2)的个数
- 根据红白蓝三色球(0,1,2)的个数重新对数组赋值
思路一代码:
#include <iostream>
using namespace std;
int const TotalColorCount = 100;
int const Red_Color = 0;
int const White_Color = 1;
int const Blue_Color = 2;
void initRandomColors(int colors[], int count){
for (int i = 0; i < count; i++) {
colors[i] = rand()%3;
}
}
void outColors(int colors[], int count)
{
for (int i = 0; i < count; i++) {
cout << colors[i];
}
cout << endl;
}
void sortColors(int colors[], int count)
{
int red_count = 0;
int white_count = 0;
int blue_count = 0;
for (int i = 0; i < count; i++) {
switch (colors[i]) {
case 0:
red_count++;
break;
case 1:
white_count++;
break;
case 2:
blue_count++;
break;
default:
break;
}
}
for (int i = 0; i < count; i++) {
if (red_count > 0) {
colors[i] = Red_Color;
red_count--;
continue;
}
if (white_count > 0) {
colors[i] = White_Color;
white_count--;
continue;
}
if (blue_count > 0) {
colors[i] = Blue_Color;
blue_count--;
continue;
}
}
}
int main(int argc, const char * argv[]) {
int colors[TotalColorCount];
initRandomColors(colors, TotalColorCount);
cout << "排序前:" << endl;
outColors(colors, TotalColorCount);
cout << "排序后:" << endl;
sortColors(colors, TotalColorCount);
outColors(colors, TotalColorCount);
return 0;
}
输出:
排序前:
1122120221020202111101021000211221201100121022210122111202011102210001111101202201012202000221021020
排序后:
0000000000000000000000000000000111111111111111111111111111111111111222222222222222222222222222222222
Program ended with exit code: 0
思路二
将数组分别三部分, 前部(0), 中部(1), 后部(2). 只需要将前部和后部的元素归位, 中部自然就排好了.
使用变量begin,end分别记录数组的开头和末尾索引.使用变量current从头遍历数组:
- 若遍历到的值为0, 则交换current和begin处的值, 同时将current和begin都向后移动一个位置, 表明begin位置前的元素已经排好;
- 若遍历到的值为1, 不需要交换, current后移一位;
- 若遍历到的值为2, 则交换current和end处的值, 由于交换完成后current处的值可能是无序的(0,1,2)都有可能, 所以current不能移动, 只将end前移一位.
思路二代码:
#include <iostream>
using namespace std;
int const TotalColorCount = 100;
int const Red_Color = 0;
int const White_Color = 1;
int const Blue_Color = 2;
void initRandomColors(int colors[], int count){
for (int i = 0; i < count; i++) {
colors[i] = rand()%3;
}
}
void outColors(int colors[], int count)
{
for (int i = 0; i < count; i++) {
cout << colors[i];
}
cout << endl;
}
void swap(int& num1, int& num2)
{
num1 = num1 + num2;
num2 = num1 - num2;
num1 = num1 -num2;
}
void sortColors(int colors[], int count)
{
int begin = 0;
int current = 0;
int end = count - 1;
while (current <= end) {
if (colors[current] == Red_Color) {
swap(colors[begin], colors[current]);
begin++;
current++;
}else if (colors[current] == White_Color) {
current++;
}else{
swap(colors[current], colors[end]);
end--;
}
}
}
int main(int argc, const char * argv[]) {
int colors[TotalColorCount];
initRandomColors(colors, TotalColorCount);
cout << "排序前:" << endl;
outColors(colors, TotalColorCount);
cout << "排序后:" << endl;
sortColors(colors, TotalColorCount);
outColors(colors, TotalColorCount);
return 0;
}