插入排序
1.插入排序的思想是比较 naive, 从第 0 个元素开始, 维护一个有序序列, 每次将当前元素插入到有序序列里面, 换句话说: 将 num[i] 插入到区间 [0, i) 使 [0, i) 成为有序数组
vector<int> insertionSort(vector<int>& nums) {
int len = nums.size();
for (int i = 1; i < len; ++i) {
// 保存当前元素的值
int tmp = nums[i];
int j = i;
// 前面比它大的往后覆盖
while (j > 0 && nums[j-1] > tmp) {
nums[j] = nums[j-1];
--j;
}
// j 找到第 1 个比 nums[i] 小的位置, 插入到这里
nums[j] = tmp;
}
return nums
}
转载请注明来源, from goldandrabbit.github.io
