[TOC] ## 概述 插入排序(InsertionSort)，一般也被称为直接插入排序。 对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。 * 基本思想：每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。 * 插入排序的**平均时间复杂度**也是 `O(n^2)`，**空间复杂度**为`常数阶 O(1)`，具体时间复杂度和数组的有序性也是有关联的。 * 插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 `N-1 `次，时间复杂度为 `O(N)`。最坏的情况是待排序数组是逆序的，此时需要比较次数最多，最坏的情况是 `O(n^2)`。 ## C++代码 ```cpp //插入排序 void insertSort(int *a, int len) { for (int i = 1; i < len; i++) { int j; int x = a[i]; //每趟将a[i]插入到前面的排序子序列中 for (j = i-1; j >= 0 && x < a[j]; j--) { a[j+1] = a[j]; //将前面较大的元素向后移动 } a[j+1] = x; //x值到达插入位置 } } int main() { int a[] = {4,1, 2, 3, 5,7, 6}; xzSort(a, 7); insertSort(a, 7); } ```