/*
插入排序:从待排序列的第2个元素开始,与前面已排序列的每个元素比较,若小(或大)则交换两元素,直到待排元素达到正确位置。
稳定性:稳定排序
时间复杂度:O(n^2)
空间复杂度:O(1)
*/
#include<iostream>
using namespace std;
int main() {
int a[15] = { 46,35,1,24,29,28,4,46,26,20,3,26,9,18,37 }; //给定数组
int len = 15; //直接给出长度
//插入排序
for (int i = 1; i < len; i++) {
for (int j = i; j > 0; j--) {
if (a[j] < a[j - 1]) {
swap(a[j], a[j - 1]); //如果小于前面的数,则交换
}
else {
break; //如果不限于前面的数,则不用交换
}
}
}
//打印输出
for (int i = 0; i < len - 1; i++) {
cout << a[i] << " ";
}
cout << a[len - 1] << endl;
return 0;
}