数据结构——插入排序算法详解（C语言）_c语言插入排序比较次数和移动次数

插入排序的算法思想是：每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适合位置上，直到所有待排序记录全部插入为止。

例如，打扑克牌在抓牌时，每抓一张牌，就插入到合适的位置，直到抓完牌为止，即得到一个有序序列。

可以选择不同的方法在已排好序的记录中寻找插入位置。根据查找方法的不同，有多种插入排序的方法 ，这里介绍三种方法：直接插入排序，折半插入排序和希尔排序。

一.直接插入排序

直接插入排序是一种最简单的排序方法，其基本操作是将一条记录插入到已排好序的有序表中，从而得到一个新的，记录数量增1的有序表。

【算法描述】（ 伪代码）

#define MAXSIZE 20//顺序表的最大长度
typedef int KeyType;//定义关键字类型为整形
typedef struct{
	KeyType key;//关键字项
	InfoType otherinfo;//其他数据项 
}RedType;//记录类型
typedef struct{
	RedType r[MAXSIZE+1];//r[0]闲置或用作哨兵单元
	int length;//顺序表长度 
}SqList;//顺序表类型
//升序排序 
void InsertSort(SqList &L)
{//对顺序表做直接插入排序
for(i=2;i<=L.length;i++)
 
	if(L.r[i].key<L.r[i-1].key)//如果待比较关键字r[i].key小于已排好序列的最后一项 
	{
		L.r[0]=L.r[i];//将 待排关键字暂放置到哨兵单元中 
		L.r[i]=L.r[i-1];//将已排好序的最后一位向后移动一个单元 
		for(j=i-2;L.r[0].key<L.r[j].key;j--)//将r[0]处的关键字依次与r[j]处的关键字进行比较 
			L.r[j+1]=L.r[j];//将r[j]向后移动一位 
		L.r[j+1]=L.r[0]; 
	}
	
 } 

【具体代码实现】

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include<windows.h>
#define MAXSIZE 30000
typedef struct
{
	int key;
	int compare;
}RedType;
typedef struct
{
	RedType r[MAXSIZE+1];
	int length;
}SqList;
long long count=0; 
 //-----------生成三万个随机数------------  
 
void sjs(SqList &L)
{
 
 	srand((unsigned)time(NULL));
 	for(int i=1;i<=MAXSIZE;i++)
 	{
 		int a=rand()%(MAXSIZE+1);
 		L.r[i].key=a; 
	 }
}
 //-----插入排序算法-------
 void InsertSort(SqList &L)
 {
 	int j;
 	L.length =(MAXSIZE);
 	for(int i=2;i<=L.length ;i++)
 	{
 		
 		if(L.r[i].key<L.r[i-1].key)
 		{
 			count++;
 			L.r[0]=L.r[i];
 			L.r[i]=L.r[i-1];
 			for(j=i-2;L.r[0].key<L.r[j].key;j--)
 			{
 				L.r[j+1]=L.r[j];
 				count++;
			 }
			 L.r[j+1]=L.r[0];
		  } 
		  else
		  {
		  	count++;
		  }
		  
	 }
 }
 int main()
 {
 	long long start,end;
 	
 	SqList L;
 	sjs(L);
 	start=GetTickCount();
 	InsertSort(L);
 	end=GetTickCount();
 	printf("从小到大排序为：\n");
 	for(int i=1;i<=MAXSIZE;i++)
 	{
 		
 		printf("%d\t",L.r[i].key);
	 }
	 printf("\n");
	 printf("插入排序运行时间为：%lldms\n",end-start);
	 printf("比较的次数为：%lld\n",count);
 }

运行结果为：

【算法分析】

（1）时间复杂度

直接插入排序的时间复杂度为O（）

（2）空间复杂度

直接插入排序只需一个记录的辅助空间r[0]，所以空间复杂度为O(1)。

【算法特点】

（1）稳定排序。

（2）算法简便，容易实现

（3）也适用于链式存储结构，只是在单链表上无需移动记录，只需修改相应的指针。

（4）更适用于基本有序的情况，当初始记录无序，n较大时，此算法复杂度较高，不宜采用。

二.折半插入排序

【算法描述】（伪代码）

#define MAXSIZE 20//顺序表的最大长度
typedef int KeyType;//定义关键字类型为整形
typedef struct{
	KeyType key;//关键字项
	InfoType otherinfo;//其他数据项 
}RedType;//记录类型
typedef struct{
	RedType r[MAXSIZE+1];//r[0]闲置或用作哨兵单元
	int length;//顺序表长度 
}SqList;//顺序表类型
//升序排序 
void InsertSort(SqList &L)
{//对顺序表做直接插入排序
for(i=2;i<=L.length;i++)
 
	{
		L.r[0]=L.r[i];//将待插入的记录暂存到监视哨中
		low=1;high=i-1;//置查找区间的初值
		while(low<=high) 
		 {
		 	m=(low+high)/2;//折半 
		 	if(L.r[0].key<L.r[m].key)high4=m-1;//插入点在前一子表 
		 	else low=m+1;//插入点在后一子表 
		 }
		 for(j=i-1;j>=high+1;j--)//记录后移 
		 L.r[j+1]=L.r[j];
		 L.r[high+1]=L.r[0];
	}
	
 } 

【具体代码实现】

//折半查找排序
#include <stdlib.h>
#include <stdio.h>
#define MAXSIZE 20
typedef struct{
	int key;
	//还可以添加其他数据型 
}RedType;
typedef struct {
	RedType r[MAXSIZE+1] ;
	int length;
}SqList;
void BInsertSort(SqList &L)
{//对顺序表L做折半插入排序
	for(int i=2;i<L.length;i++)
	{
		L.r[0]=L.r[i];
		int low=1;
		int high=i-1;
		while(low<=high)
		{
			int m=(low+high)/2;	
			if(L.r[0].key<L.r[m].key)
			{
				high=m-1;
			}
			else
			{
				low=m+1;
			}
		}
			for(int j=i-1;j>=high+1;j--)
			{
				L.r[j+1]=L.r[j];
			}
			L.r[high+1]=L.r[0];
			} 
	
 } 
 int main()
 {
 	SqList L;
 	printf("输入数据的个数为：\n");
 	scanf("%d",&L.length);
 	printf("请输入数据（用空格隔开）\n");
	 for(int i=1;i<=L.length;i++)
	 {
	 	scanf("%d",&L.r[i].key);
	  } 
	  BInsertSort(L);
	  printf("排序的结果为：\n");
	  for(int i=1;i<=L.length;i++)
	 {
	 	printf("%d ",L.r[i].key);
	  } 
 }

运行结果为：

【算法分析】

（1）时间复杂度： O（）

  (2) 空间复杂度：与直接插入排序相同，只需要一个记录的辅助空间，所以空间复杂度为O（1）

【算法特点】

（1）稳定排序。

（2）因为要进行折半查找，所以只能用于顺序结构，不能用于链式结构。

（3）适合初始记录无序，n较大时的情况。

三.希尔排序

希尔排序又称“缩小增量排序”，是插入排序的一种。直接插入排序，当待排序的记录个数较少且待排序序列的关键字基本有序时，效率较高。希尔排序基于以上两点，从“减少记录个数”和“序列基本有序”两个方面对直接插入排序进行了改进。但希尔排序是非稳定排序算法。

【算法步骤】

希尔排序实质上是采用分组插入的方法。其基本思想是：先将整个待排序列分割成几组，从而减少参与直接插入排序的数据量，对每组分别进行直接插入排序，然后增加每组的数据量，重新分组。这样当经过几次分组排序后，整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。

举例：已知待排序的关键字序列为｛49，38，65，97，76，13，27，49，55，04｝，则用希尔排序法进行排序的过程为（增量选取5，3，1）：

 【具体代码实现】

//希尔排序 
#include <stdlib.h>
#include <stdio.h>
#define MAXSIZE 20
 
typedef struct{
	int key;
	//还可以添加其他数据型 
}RedType;
typedef struct {
	RedType r[MAXSIZE+1] ;
	int length;
}SqList;
void ShellInsert(SqList &L,int dk)
{
	int j,i; 
	for(i=dk+1;i<=L.length;i++)
	if(L.r[i].key<L.r[i-dk].key)
	{
		L.r[0]=L.r[i];
		for(j=i-dk;j>0&& L.r[0].key<L.r[j].key;j-=dk)
		L.r[j+dk]=L.r[j];
	L.r[j+dk]=L.r[0];
	}
 } 
 void ShellSort(SqList &L,int dt[],int t)
 {
 	for(int k=0;k<t;k++)
 	{
 		ShellInsert(L,dt[k]);
	  } 
  } 
  int main()
  {
  	SqList L;
  	int t=3;
  	int dt[3]={5,3,1};
  	printf("输入数据的个数为：\n");
 	scanf("%d",&L.length);
 	printf("请输入数据（用空格隔开）\n");
	 for(int i=1;i<=L.length;i++)
	 {
	 	scanf("%d",&L.r[i].key);
	  } 
	  ShellSort(L,dt,3);
	  printf("排序的结果为：\n");
	  for(int i=1;i<=L.length;i++)
	 {
	 	printf("%d ",L.r[i].key);
	  } 
  }

【算法分析】

（1）时间复杂度：有人在大量的试验基础上推出：当n在某一个特定范围内，希尔排序所需的比较和 移动次数约为n^1.3

(2)空间复杂度：O(1)

【算法特点】

（1）排序方法不稳定。

（2）只能用于顺序，不能用于链式。

（3）1记录总的比较次数和移动次数都比直接插入排序要少，n越大，效果越明显 。