排序算法-插入排序法（InsertSort）

1、说明

插入排序法是将数组中的元素逐一与已排序好的数据进行比较，先将前两个元素排序好，再将第三个元素插入适当的位置，也就是说这三个元素仍然是已排序好的，接着将第四个元素加入，重复此步骤，直到排序完成为止。可以看作是在一串有序的记录R1,R2,...,Ri中插入新纪录R，使得i+1个记录排序妥当。

2、算法分析

最坏情况和平均情况均需比较： $(n-1)+(n-2)+(n-3)+...+3+2+1=\frac{n(n-1)}{2}$ 次，时间复杂度为 $O(n^{2})$ 。最好情况时间复杂度为 $O(n)$ 。
插入排序是稳定排序法。
因为只需一个额外的空间，所以空间复杂度为最佳。
这种排序法适用于大部分数据已经过排序的情况，也适用于往已排序数据库中添加新数据后再进行排序的情况。
由于插入排序法会造成数据的大量搬移，因此建议在链表上使用。

3、C++代码

#include<iostream>
using namespace std;int main() {int data[6] = { 9,7,5,3,4,6 };cout << "原始数据：" << endl;for (int i = 0; i < 6; i++) {cout << data[i] << "  ";}cout << endl;int i;int j;//第1次：//7  9  5  3  4  6//第2次：//5  7  9  3  4  6//第3次：//3  5  7  9  4  6//第4次：//3  4  5  7  9  6//第5次：//3  4  5  6  7  9for (i = 1; i < 6; i++) {int temp = data[i];j = i - 1;//temp > data[j]	从大到小排序的条件//temp < data[j]	从小到大排序的条件while (j >= 0 && temp < data[j]) {data[j + 1] = data[j];j--;}data[j + 1] = temp;}cout << "最终数据：" << endl;for (int i = 0; i < 6; i++) {cout << data[i] << "  ";}cout << endl;return 0;
}

输出结果