首页 > 代码库 > Sort colors系列

Sort colors系列

75. Sort Colors

问题描述:

给一个包含n个数字的数组,其中有0,1,2;排序使得所有相同的数字相邻,且按照0,1,2的顺序。

思路:

(1)计数排序:

  需要扫两遍数组,一遍统计个数,第二遍开始摆放数字。

代码如下:

 

 1 void sortColors(vector<int>& nums) {
 2         int i=0,j=0,k=0;
 3         int n=nums.size();
 4         for(int p=0;p<n;p++)
 5         {
 6             if(nums[p]==0)
 7                 i++;
 8             else if(nums[p]==1)
 9                 j++;
10             else
11                 k++;
12         }
13         for(int p=0;p<n;p++)
14         {
15             if(p<i)
16                 nums[p]=0;
17             else if(p>=i&& p<i+j)
18                 nums[p]=1;
19             else
20                 nums[p]=2;
21         }
22     }

(2)如果只能扫一遍,很容易想到的就是左边存放0和1,右边存放2.两边往中间靠。

设置两个index,left记录第一个1的位置,left左边为0,right记录第一个非2的位置,right右边为2.

然后使用i从头到尾扫一遍,直到与right相遇。

i遇到0就换到左边去,遇到2就换到右边去,遇到1就跳过。

需要注意的是:由于left记录第一个1的位置,因此A[left]与A[i]交换后,A[left]为0,A[i]为1,因此i++;

而right记录第一个非2的位置,可能为0或1,因此A[right]与A[i]交换后,A[right]为2,A[i]为0或1,i不能前进,要后续判断。

由此该数组分为4段:[0,left)-->0; [left,i)-->1; [i,right]-->乱序; (right,n-1]-->2

0  0  0  1  1  1  2  1  0  2  1  2  2  2

           ^         ^             ^

          left         i            right

最直接的方法就是partition方法,代码如下:

 1 void sortColors(int A[], int n) {
 2         int left = 0;
 3         int right = n-1;
 4         int i = 0;
 5         while(i <= right)
 6         {
 7             if(A[i] == 0)
 8             {
 9                 swap(A[left], A[i]);
10                 left ++;
11                 i ++;
12             }
13             else if(A[i] == 1)
14             {
15                 i ++;
16             }    
17             else
18             {
19                 swap(A[i], A[right]);
20                 right --;
21             }
22         }
23     }

(3)最漂亮的一种做法:

【最直观:平移插入】

 1 void sortColors(int A[], int n) {
 2         int i = -1;
 3         int j = -1;
 4         int k = -1;
 5         for(int p = 0; p < n; p ++)
 6         {
 7             //根据第i个数字,挪动0~i-1串。
 8             if(A[p] == 0)
 9             {
10                 A[++k] = 2;    //2往后挪
11                 A[++j] = 1;    //1往后挪
12                 A[++i] = 0;    //0往后挪
13             }
14             else if(A[p] == 1)
15             {
16                 A[++k] = 2;
17                 A[++j] = 1;
18             }
19             else
20                 A[++k] = 2;
21         }
22 
23     }

 

Sort colors系列