C++之荷兰国旗问题

问题描述

现有红白蓝三个不同颜色的小球,乱序排列在一起,请重新排列这些小球,使得红白蓝三色的同颜色的球在一起. 之所以被称为荷兰国旗问题, 是因为荷兰国旗正好有红白蓝三种颜色构成, 将红白蓝三色小球想象成条状物,有序排列后正好组成荷兰国旗.

问题分析

荷兰国旗问题其实是一个数组排序问题, 可以将红白蓝三种颜色分别用数字0,1,2表示, 然后对数组中的数值进行排序.

问题解决

思路一

  1. 遍历数组, 统计红白蓝三色球(0,1,2)的个数
  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从头遍历数组:

  1. 若遍历到的值为0, 则交换current和begin处的值, 同时将current和begin都向后移动一个位置, 表明begin位置前的元素已经排好;
  2. 若遍历到的值为1, 不需要交换, current后移一位;
  3. 若遍历到的值为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;
}