# [LeetCode]75.Sort Colors

#### 【题目】

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?

#### 【分析】

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

#### 【代码】

    /**------------------------------------
*   日期：2015-02-02
*   作者：SJF0115
*   题目: 75.Sort Colors
*   网址：https://oj.leetcode.com/problems/sort-colors/
*   结果：AC
*   来源：LeetCode
*   博客：
---------------------------------------**/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
void sortColors(int A[], int n) {
if(n <= 1){
return;
}//if
// 统计个数
int red = 0,white = 0,blue = 0;
for(int i = 0;i < n;++i){
if(A[i] == 0){
++red;
}//if
else if(A[i] == 1){
++white;
}//else
else{
++blue;
}//else
}//for
// 重新布局
for(int i = 0;i < n;++i){
if(red > 0){
A[i] = 0;
--red;
}//if
else if(white > 0){
A[i] = 1;
--white;
}//else
else{
A[i] = 2;
}
}//for
}
};

int main(){
Solution s;
int A[] = {0,0,1,0,2,0,1,2};
s.sortColors(A,8);
for(int i = 0;i < 8;++i){
cout<<A[i]<<endl;
}//for
// 输出
return 0;
}


#### 【思路二】

A[i] == 2，直接插入blue

#### 【代码二】

    /**------------------------------------
*   日期：2015-02-03
*   作者：SJF0115
*   题目: 75.Sort Colors
*   网址：https://oj.leetcode.com/problems/sort-colors/
*   结果：AC
*   来源：LeetCode
*   博客：
---------------------------------------**/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
void sortColors(int A[], int n) {
if(n <= 1){
return;
}//if
int red = -1,white = -1,blue = -1;
for(int i = 0;i < n;++i){
// 插入red对white blue有影响
if(A[i] == 0){
// blue整体向后移动一位
A[++blue] = 2;
// white整体向后移动一位
A[++white] = 1;
// 插入red
A[++red] = 0;
}//if
// 插入white blue受到影响
else if(A[i] == 1){
// blue整体向后移动一位
A[++blue] = 2;
// 插入white
A[++white] = 1;
}//else
// 插入blue对其他没有影响
else{
// 插入blue
A[++blue] = 2;
}//else
}//for
}
};

int main(){
Solution s;
int A[] = {0,0,1,0,2,0,1,2};
s.sortColors(A,8);
for(int i = 0;i < 8;++i){
cout<<A[i]<<endl;
}//for
// 输出
return 0;
}


#### 【思路三】

class Solution {
public:
void sortColors(int A[], int n) {
for(int i=0;i<n;i++){
for(int j=0;j<n-i-1;j++){
if(A[j]>A[j+1]){
int tmp=A[j];
A[j]=A[j+1];
A[j+1]=tmp;
}
}
}
}
};

#### 【思路四】

（1）若遍历到的位置为1，则说明它一定属于中部，根据总思路，中部的我们都不动，然后current向前移动一个位置。

（2）若遍历到的位置为0，则说明它一定属于前部，于是就和begin位置进行交换，然后current向前移动一个位置，begin也向前移动一个位置（表示前边的已经都排好了）。

（3）若遍历到的位置为2，则说明它一定属于后部，于是就和end位置进行交换，由于交换完毕后current指向的可能是属于前部的，若此时current前进则会导致该位置不能被交换到前部，所以此时current不前进。而同1），end向前移动一个位置。

#### 【代码四】

    /**------------------------------------
*   日期：2015-02-04
*   作者：SJF0115
*   题目: 75.Sort Colors
*   网址：https://oj.leetcode.com/problems/sort-colors/
*   结果：AC
*   来源：LeetCode
*   博客：
---------------------------------------**/
class Solution {
public:
void sortColors(int A[], int n) {
int begin = 0,end = n-1,cur = 0;
while(cur <= end){
if(A[cur] == 0){
swap(A[begin],A[cur]);
// 指向排序0末尾的下一个位置
++begin;
// 向前遍历
++cur;
}//if
else if(A[cur] == 1){
++cur;
}//else
else{
swap(A[end],A[cur]);
// 指向排序2开头的前一个位置
--end;
}//else
}//for
}
};


+ 订阅