[数据结构与算法]内部排序 - 直接插入排序

内部排序——直接插入排序

一、算法思想

每次将一个待排序的记录按其关键字大小插入前面已排好的子序列，直到全部记录插入完成。

二、插入排序算法

? 采用在 r[0] 设置“哨兵”的方法，目的为了减少比较次数。

//直接插入排序 
 void InsertSort(RecordType r[],int length){
 	int i,j;
 	for(i = 2;i<=length;i++){
 		r[0] = r[i]; 	 //将待插入数据放入监视哨中 
 		j = i-1;		 //从待插入数据的前一个位置开始寻找 
 		while(r[0].key < r[j].key){	//寻找插入位置 
 			r[j+1] = r[j];
 			j--;
		 }
		 r[j+1] = r[0];	  //将待插入数据放入已排序的序列中 
	 }
 	
 }

?

三、性能分析

1. 空间效率：仅使用了常数个辅助单元，因而空间复杂度为 O(1)。

2. 时间效率：

   1. 在最好情况下，表中元素已经有序，此时每插入一个元素，都只需要比较而不需要移动元素，因而时间复杂度为 O(n)。

   2. 在最坏情况下，表中元素逆序，总的比较次数与移动次数都达到最大，因此时间复杂度为 O(n^2)。

3. 稳定性：由于每次插入元素时总是从后向前比较移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是稳定的排序算法。

四、完整代码

#include<stdio.h>
#include<stdlib.h>

typedef int KeyType;
typedef int OtherType;

//结构体
 typedef struct reccord {
 	KeyType key;
 	OtherType other_data;
 	
 }RecordType;
 
 //直接插入排序 
 void InsertSort(RecordType r[],int length){
 	int i,j;
 	for(i = 2;i<=length;i++){
 		r[0] = r[i]; 	//将待插入数据放入监视哨中 
 		j = i-1;		//从待插入数据的前一个位置开始寻找 
 		while(r[0].key < r[j].key){	//寻找插入位置 
 			r[j+1] = r[j];
 			j--;
		 }
		 r[j+1] = r[0];			//将待插入数据放入已排序的序列中 
	 }
 	
 }


int main(){
	
	RecordType r[20];
	int len;	//待排序数组长度
	printf("请输入待排序数组长度：");
	scanf("%d",&len);
	
	
	for(int i = 1;i <= len;i++){
		printf("请输入第%d个数据:",i);
		fflush(stdin);
		scanf("%d",&r[i].key);
	}
	printf("初始化数据为：");
	for(int i = 1;i <= len;i++){
		printf("%d ",r[i].key);
	}
	
	InsertSort(r,len);
	printf("\n排序后数据为：");
	for(int i = 1;i <= len;i++){
		printf("%d ",r[i].key);
	}
	
	
}

五、运行截图