数组中只有0,1,2三种元素，要求原地排序，不能使用额外的空间

数组中只有0,1,2三种元素，要求原地排序，不能使用额外的空间 ，并且一次遍历完成。

解析：

对于数组中只包含0、1、2三种元素，并且要求原地排序且不能使用额外空间的问题，我们可以采用荷兰国旗问题的解决方案。这种方法可以在不使用额外数组的情况下，将数组中的元素重新排列。

1. 分析与思考：
   • 我们使用三个指针：low、mid和high。low指向数组的起始位置，mid也从数组的起始位置开始遍历，high指向数组的末尾。
   • 当mid指向的元素为0时，我们将其与low指向的元素交换，并将low和mid都向右移动一位。
   • 当mid指向的元素为2时，我们将其与high指向的元素交换，但此时只将high向左移动一位，因为交换过来的元素可能还需要检查。
   • 当mid指向的元素为1时，我们只需要将mid向右移动一位。
   • 重复上述步骤，直到mid超过high。

代码：

#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;
#include <vector>

/*
数组中只有0,1,2三种元素，要求原地排序，不能使用额外的空间。
*/

#include <vector>
#include <iostream>

void sortColors(std::vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;
    while (mid <= high) {
        if (nums[mid] == 0) {
            std::swap(nums[low], nums[mid]);
            low++;
            mid++;
        } else if (nums[mid] == 2) {
            std::swap(nums[mid], nums[high]);
            high--;
        } else {
            mid++;
        }
    }
}

int main() {
    std::vector<int> nums = {2, 0, 2, 1, 1, 0, 1, 0, 2, 1, 0};
    sortColors(nums);
    for (int num : nums) {
        std::cout << num << " ";
    }
    system("pause");
    return 0;
}