一、题目描述
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
二、解题方案
一、冒泡法
- 原理：相邻两个数进行比较，如果前面比后面的大，则进行交换。（稳定排序）
- 学习冒泡法的同时，让我想起了神秘巨星的一句台词
你会成为巨星的，就像苏打水里的气泡，浮上来完全靠自己。（神秘巨星）
void sortColors(vector<int>& nums) {
for (int i = 0; i < nums.size()-1; i++) {
for (int j = 0; j < nums.size()-i-1; j++) {
if (nums[j] > nums[j+1]) {
//swap(nums[j], nums[j + 1]);
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
}
二、选择排序
- 原理：第一次从待排序的数据元素中，选出最小（大）的的一个元素，与起始位置相交换，然后再依此类推直至拍完。
void sortColors2(vector<int>& nums) {
for (int i = 0; i < nums.size(); i++) {
int min = i;
for (int j = i+1; j < nums.size(); j++) {
if (nums[min] > nums[j]) {
min = j;
}
}
if (min != i) {
int temp = nums[i];
nums[i] = nums[min];
nums[min] = temp;
}
}
}
三、其他方案
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
void sortColors3(vector<int>& nums) {
vector<int>::iterator it;
int i = 0, j = 0, k = 0;
for (it = nums.begin(); it != nums.end();it++) {
if (*it == 0) {
i++;
}else if(*it == 1){
j++;
}
else if (*it == 2) {
k++;
}
}
for (it = nums.begin(); it != nums.end(); it++) {
if (i != 0) {
i--;
*it = 0;
}
else if (j != 0) {
j--;
*it = 1;
}
else if (k != 0) {
k--;
*it = 2;
}
}
}