🔥码云GVP开源项目 12k star Uniapp+ElementUI 功能强大 支持多语言、二开方便! 广告
[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); } ```