插入排序是基础简单,同时效率也不高的排序
void insertion_sort(vector<int>& nums) {
int n = nums.size();
// 把第一个当作是有序序列,从第二个开始操作
for (int i = 1; i < n; i++) {
int j = i;
while (j>0&&nums[j] < nums[j - 1]) {
swap(nums[j], nums[j - 1]);
j--;
}
}
}
int main() {
vector<int> nums = { 2,8,1,5,3,9,6 };
insertion_sort(nums);
for (int i : nums) cout << i << " ";
return 0;
}
随手写一个,可以看出其实还是基于比较并交换的排序
最坏时间复杂度应该是在O(N^2^)
级别,最好是一次遍历无需交换,原地排序空间复杂度O(1)