插入排序思路总结以及算法性能分析

（一）思路：

首先大家先和我看一张图，是我从leetcodes上保存下来的

思路图

1.声明一个待插入数temp
2.待插入数前面的序列为待插入序列
3.循环：待插入数从第二个数开始，从序列的最后一位开始比较，符合循环条件就向后移动一位
4.循环结束，将待插入数，赋值给移除的“空位”

（二）代码测试：

#include <stdio.h>
#include <string.h>
void sort(int *arr){
    int temp;//待插入数
    int i,j;
    for(i=1;i<9;i++)
    {
        temp=arr[i];
        j=i-1;//插入序列为该数前面的序列
        while(j>=0&&temp<arr[j])
        {
            //符合条件则向后移动一位
            arr[j+1]=arr[j];
            --j;
        }
        arr[j+1]=temp;//移出的空位插入
    }
}
int main(){
    int arr[9]={1,3,4,1,9,23,4,4,6};
    sort(arr);
    for(int i=0;i<9;i++)
    {
        printf("%d ",arr[i]);
    }
}

测试结果

（三）算法性能分析：

时间复杂度分析

1.确定向后移动一位arr[j+1]=arr[j]为基本操作
2.j的长度：子序长度为规模，则最外层n次循环
对应的基本操作次数：

如图： 时间复杂度

空间复杂度

因为该算法的辅助存储空间不随排序序列的规模的变化而变化，是个常量，因此空间复杂度为O(1)。