算法1
计数排序
开三个变量分别统计 0, 1, 2
的个数
最后再把数组重写一遍
时间复杂度
$O(n)$
空间复杂度
$O(1)$
C语言 代码
void sortColors(int* nums, int numsSize) {
int count0 = 0, count1 = 0, count2 = 0; // 分别统计0 1 2有多少个
for(int i = 0; i < numsSize; i++){
if(nums[i] == 0){
count0 ++;
}else if(nums[i] == 1){
count1 ++;
}else{
count2 ++;
}
}
int i = 0;
// 重写nums 先写count0个0 再写count1个1 最后写count2个2
for(int j = 0; j < count0; j++){
nums[i++] = 0;
}
for(int j = 0; j < count1; j++){
nums[i++] = 1;
}
for(int j = 0; j < count2; j++){
nums[i++] = 2;
}
}
算法2
三指针算法
算法思路
时间复杂度
$O(n)$
仅一趟遍历就可以完成排序
空间复杂度
$O(1)$
C语言 代码
void swap(int* nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
void sortColors(int* nums, int numsSize) {
for(int i = 0, j = 0, k = numsSize - 1; i <= k;){
if(nums[i] == 0){
swap(nums, i, j);
i++, j++;
}else if(nums[i] == 1){
i++;
}else{
swap(nums, i, k);
k--;
}
}
}