插入排序

原数组为915623

 1 void print(vector<int>& a, int n, int i) {
 2     cout << "step" << i << ": ";
 3     for (int j = 0; j < n; j++) {
 4         cout << a[j] << " ";
 5     }
 6     cout << endl;
 7 }
 8 void insertionSort(vector<int>& a, int n) {//{ 9,1,5,6,2,3 }
 9     for (int i = 1; i < n; ++i) {
10         if (a[i] < a[i - 1]) { //若第i个元素⼤于i-1元素，直接插⼊。⼩于的话，移动有序表后插⼊
11                 int j = i - 1;
12             int x = a[i]; //复制为哨兵，即存储待排序元素
13             //a[i] = a[i - 1]; //先后移⼀个元素，可以不要这⼀句，跟循环⾥⾯的功能᯿复了
14                 while (j >= 0 && x < a[j]) { //查找在有序表的插⼊位置,还必须要保证j是>= 0的 因为a[j]要合法
15                         a[j + 1] = a[j];
16                     j--; //元素后移
17                 }
18             a[j + 1] = x; //插⼊到正确位置
19         }
20         print(a, n, i); //打印每趟排序的结果
21     }
22 }