插入排序(升序)复杂度分析

可以把插入排序想象成抽扑克牌，从牌堆中每抽一张牌我们就和手牌比较并插入。
一般，我们习惯大牌放左边，小牌放右边，那么我们抽牌时从左往右（或从右
往左）把抽的牌和手牌对比，找到，放入手牌，这个过程就可以看作时插入排序

1.代码实现

插入排序代码实现比较简单

#include "iostream"
#include "cassert"
using namespace std;

void swap(int *a1,int *a2){
    int tmp = *a1;
    *a1=*a2;
    *a2=tmp;
}
//默认升序
void insert_sort(int* a,int n) {
    assert(a);
    int end_index = n - 1;
    for (int i = 1; i <= end_index; i++) {
        for (int tail = i - 1; tail >= 0; tail--)
            if (a[tail] > a[tail + 1])
                swap(&a[tail], &a[tail + 1]);
            else
                break;
    }
}
int main(){
    int a[10]={4,1,7,5,9,3,8,0,1,2};
    insert_sort(a,10);
    for(auto i:a){
        cout<<i<<' ';
    }
    return 0;
}

运行结果:

0 1 1 2 3 4 5 7 8 9
进程已结束，退出代码为 0

• 函数参数a是数组，n时数组大小
• end_index是数组末元素索引
• i从第二个元素开始遍历（如果没有第二个，整个函数结束）
• tail为有序数列末元素，拿tail和tail+1作比较，如果降序就交换位置

2.复杂度分析

先说结果：

最优时间复杂度：O(N)（数组本就有序）
最差时间复杂度：O(N^2)
空间复杂度：O(1)

空间复杂度为1可以理解，插入排序函数另外需要的变量空间为常数个

时间复杂度分析

我们默认得到升序，最坏的情况莫过于需要插入的数和有序数列的每一个都对比---数列是降序的
那么，假设有n个数

• 第2个数需要和前面的数对比1次
• 第3个数需要和前面的数对比2次
• 第4个数需要和前面的数对比3次
• 。。。
• 第n个数需要和前面的数对比n-1次
• 总共次数=(1+n-1)*n/2=n^2/2
• 则时间的复杂度O(n^2)