织梦移动网站模板网站收录入口

75. 颜色分类 - 力扣（LeetCode）

题目不追求稳定 可以选择选择排序

这是我没看教程代码之前写的 有点复杂了 我还把元素后移了

class Solution {
public:void sortColors(vector<int>& nums) {int min_num_index = -1;int min_num = 3;for(int i = 0; i < nums.size(); ++i ){  //确保全部有序for (int j = i; j < nums.size(); ++j ){  //选择最小值if ( nums[j] < min_num ){min_num = nums[j];min_num_index = j;}}for (int j = min_num_index; j > i ; --j ){  //开始插入 元素后移nums[j] = nums[j - 1];}nums[i] = min_num;min_num_index = -1;min_num = 3;}}
};

其实可以直接交换位置就可以

将起始位置和最小元素交换 就可以了

实现如下

class Solution {void selectionSort( 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[j] < nums[min]){min = j;}}//找到最小元素 和第一个未排序的交换位置int tmp = nums[i];nums[i] = nums[min];nums[min] = tmp;}}
public:void sortColors(vector<int>& nums) {selectionSort(nums);}
};