75. 顏色分類 - 力扣（LeetCode）

題目不追求穩(wěn)定 可以選擇選擇排序

這是我沒看教程代碼之前寫的 有點復雜了 我還把元素后移了

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;}}
};

其實可以直接交換位置就可以

將起始位置和最小元素交換 就可以了

實現(xiàn)如下

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);}
};