算法-排序之插入排序

插入排序是一种简单的排序算法，这是一种从小范围到大范围的递归思想,这种思想类似于数学推导中的递归，首先在最小规模n（1个数的队列）满足要求，再考虑n+1时需要的操作，递归直到最终的结果。当问题规模很大无从下手时，在问题最小规模点思考，然后逐渐递加，不失为一个很好的选择。

1.插入排序InsertSort

核心：以一个人为初始序列，从第二个人开始每次将一个人插入该队列中

明白了插入排序的核心，你能轻易理解插入排序的步骤：

1.将第一个数作为起始序列

2.将下一个数插入序列，

3.直到所有数全部插入序列，得到完整有序结果

以3为起始序列，分成如下

将9插入左边的序列

将5插入左边的序列

左边的有序序列会慢慢将右边的序列全部包含，最后左边的序列便是我们需要最终有序结果。需要注意的是，在插入数时，需要根据插入数的大小找到相应的插入位置。

下面是可复制代码：

void InsertSort(int Array[],int num){

int i; //控制排序遍数

int m; //控制插入

for(i=1;i<num;i++){

int temp=Array[i]; //保存要插入有序列的数

m=i-1; //此时有序列有i-1个数

while(m>=0 && Array[m]>temp){

Array[m+1]=Array[m];

m--; //将比要插入数大的往后移动一位

}

Array[m+1]=temp; //空出来位置的插入插入数

}

InsertSort.c

2.时间复杂度

O(n*2)，插入排序的时间复杂度分析较为复杂，有兴趣可以探究一下。

3.空间复杂度

一个额外交换空间，O(1)。

顶
9


踩