leetcode75. Sort Colors

核心思想

• 插入排序

class Solution {
public:
    void sortColors(vector<int>& nums) {
        for (int i = 1; i < nums.size(); i++) {
            int tmp = nums[i];
            int j = i - 1;
            while (j >= 0) {
                if (nums[j] > tmp) {
                    nums[j+1] = nums[j];
                }
                else {
                    break;
                }
                j--;
            }
            //  这里犯了一个很傻的错误， 写成了 j++，leetcode网站一直报overflow，搞得我莫名其妙
            // 这里应该先加1，然后在赋值。
            nums[++j] = tmp;
        }
    }
};

将代码简化一下，速度更快

class Solution {
public:
    void sortColors(vector<int>& nums) {
        for (int i = 1; i < nums.size(); i++) {
            int tmp = nums[i];
            int j = i - 1;
            while (j >= 0 && nums[j] > tmp) {
                nums[j + 1] = nums[j];
                j--;
            }
            // 如果j == -1 or nums[j] <= tmp 才会推出while，此时j应该先加上一才是tmp的插入位置
            nums[++j] = tmp;
        }

        for (auto &item : nums) {
            cout << item << endl;
        }
    }
};