2.插入排序

 1 #include "pch.h"
 2 #include <iostream>
 3 void InsertionSort(int *a, int len)
 4 {
 5     for (int j = 1; j < len; j++)
 6     {
 7         int key = a[j];              //从第二个元素开始，左边为已排序序列
 8         int i = j - 1;               //记录已排序序列最后一个元素的下标
 9         while (i >= 0 && a[i] > key) //从后往前，使下一个选择的元素与每一个已排序元素比较
10         {                            //只要比选择的元素大就后移，直到首次小于它的元素，插入该位置
11             a[i + 1] = a[i];
12             i--;
13         }
14         a[i + 1] = key;
15     }
16 }
17 int main() {
18     int a[8] = { 4,2,3,7,6,9,8,5 };
19     InsertionSort(a, 8);
20     for (int k = 0; k < 8; k++) {
21         std::cout << a[k] << " ";
22     }
23 }