什么是直接插入排序？

直接插入排序是一种最简单的排序方法，其基本操作是将需要排序的元素插入到已排好的有序表序列中，从而得到一个完整的有序序列。

算法思想

①将待排序序列分为两部分，一部分有序一部分无序。
②我们把第一个元素看作有序序列，从第二个元素到最后为无序序列。
③将无序序列中每一个元素依次插入到有序序列的合适位置–从小到大（从大到小）。

实例讲解

我们有一个待排序序列为【3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48】

1、我们将第一个元素3看成已经排序好的序列，即有序序列。
2、从第二个元素44到最后一个元素48我们看作为无序的的序列，即待排序的序列。

3、我们将待排序序列中的第一个元素【44】，插入到有序序列中。
①待排序元素【44】和有序序列中元素【3】进行比较，【44】比【3】大则直接插入到有序序列中。

②此时有序序列为【3,44】，待排序序列为【38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48】

3、我们将待排序序列中的第一个元素【38】，插入到有序序列中。
①待排序元素【38】和有序序列中元素【44】进行比较，【38】比【44】小，则将【44】向后移动，然后在将【38】和【3】进行比较，【38】大于【3】则将元素【38】插入到【3】位置后。
注意： 需要将待排序元素与有序序列中的每一个元素进行比较。

②此时有序序列为【3,38,44】，待排序序列为【 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48】

4、然后按照以上操作，将待排序序列中的元素依次插入到有序列中。

---

小结：
待排序元素比有序元素元素大则直接插入到该有序元素后，若小于有序元素则将该有序元素向后移动。

算法分析

时间复杂度

O(n²)

空间复杂度

O(1)

稳定性

稳定的排序算法，其稳定性在于相同值的元素进行插入排序完成后相对位置不发生改变。

代码实现

#include<stdio.h>
void Print(int array[],int len){
	for(int i=0;i<len;i++){
		printf("%d ",array[i]);
	}
	printf("\n");
} 
/*直接插入排序*/
/*
*算法描述：
*1.将待排序序列分为两部分，一部分有序一部分无序
*2.第一个元素为有序序列，从第二个元素到最后为无序序列 
*3.将无序序列中每一个元素依次插入到有序序列的合适位置--从小到大（从大到小） 
*合适的位置：待排序元素大于或等于（小于）该元素 
*/ 
void InsertSort(int array[],int len){
	int i,j;
	//第一个for循环 遍历无序序列 
	for(i=1;i<len;i++){  //从数组的第二个元素开始依次遍历无序序列 
	 	int tem = array[i];  //临时保存将要排序的元素 
	 	//第二个for循环遍历有序序列 
	 	for(j=i-1;tem<=array[j]&&j>=0;j--){  //将待排序元素依次和有序序列中的元素比较 
	 		//待排序元素 小于 有序序列中当前元素时 将该元素后移
	 		array[j+1] = array[j];
	 	}
	array[j+1] = tem;  //待排序元素 大于 有序序列最后一个元素 直接将该元素插入到有序序列最后 
	}
	printf("\n排序完成!\n\n");
}

main(){ 
	int array[10] = {4,3,10,5,6,7,1,2,8,9} ;
	int len = sizeof(array) / sizeof(int);
	printf("初始序列：\n");
	Print(array,len);
	InsertSort(array,len);
	printf("排序后序列：\n");
	Print(array,len);
}

运行结果