給定一個(gè)包含紅色泪喊、白色和藍(lán)色棕硫，一共 n個(gè)元素的數(shù)組， 原地對(duì)它們進(jìn)行排序袒啼，使得相同顏色的元素相鄰哈扮，并按照紅色纬纪、白色、藍(lán)色順序排列滑肉。
此題中包各，我們使用整數(shù) 0、 1 和 2 分別表示紅色靶庙、白色和藍(lán)色问畅。
注意:
不能使用代碼庫(kù)中的排序函數(shù)來(lái)解決這道題。
示例:
輸入: [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2]
進(jìn)階：
- 一個(gè)直觀的解決方案是使用計(jì)數(shù)排序的兩趟掃描算法惶洲。
首先按声，迭代計(jì)算出0、1 和 2 元素的個(gè)數(shù)恬吕，然后按照0签则、1、2的排序铐料，重寫(xiě)當(dāng)前數(shù)組渐裂。 - 你能想出一個(gè)僅使用常數(shù)空間的一趟掃描算法嗎？
基數(shù)排序法
可以采用基數(shù)排序法的思想钠惩，用一個(gè)數(shù)組記錄下 0柒凉，1，3 的次數(shù)篓跛，后重排膝捞，這個(gè)算法對(duì)數(shù)組進(jìn)行了兩次遍歷。
C++1
class Solution {
public:
void sortColors(vector<int>& nums) {
vector<int> temp(3,0);
for(int i=0;i<nums.size();i++){
temp[nums[i]]+=1;
}
int j=0;
int index=0;
while(j<3){
for(int k=0;k<temp[j];k++){
nums[index++] = j;
}
j++;
}
}
};
一次循環(huán)排序的方法
c++2
三路快速排序方法
設(shè)置三個(gè) lt, gt, i 定義：nums[0...lt] == 0愧沟，nums[lt+1...i-1] = 1蔬咬，nums[gt...n-1] == 2，遍歷一遍改數(shù)列保持這個(gè)定義沐寺。
C++3
class Solution {
public:
void sortColors(vector<int>& nums) {
int len = nums.size();
int lt=-1, gt=len, i=0;
while(i<gt){
if(nums[i] == 0){
lt++;
int temp = nums[i];
nums[i] = nums[lt];
nums[lt] = temp;
i++;
}
else if(nums[i] == 2){
gt--;
int temp = nums[i];
nums[i] = nums[gt];
nums[gt] = temp;
}
else{
i++;
}
}
}
};
