直接插入排序 C语言实现

今天药忘吃喽~ 2022-12-22 09:46 120阅读 0赞

### 直接插入排序 ###

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

**算法步骤：**

（1）设待排序的记录存放在数组Data\[1…n\]中，Data\[1\]是一个有序序列。  
（2）循环n-1次，每次使用顺序查找法，查找Data\[ \]（i = 2，…，n）在已排好序的序列Data\[ 1…i-1 \]中插入位置，然后将Data\[i\]插人表长为i-1的有序序列Data\[ 1…i-1 \]，直到将Data\[n\]插人表长为n-1的有序序列Data\[ 1…n-1 \]，最后得到一个表长为n的有序序列。

**书上的例子**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]  
**时间复杂度**

最好情况：O(n)  
最坏情况：O( n 2 n^2 n2)  
平均情况：O( n 2 n^2 n2)

**空间复杂度**

O(1)

**稳定性**

稳定

**完整代码如下：**

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXSIZE 100 //顺序表最大容量，可以自行加大 
    
    typedef struct 
    { 
    	int key;//关键字项 
    	char *otherinfo;//其他数据项 
    }ElemType;//记录类型 
    typedef struct
    { 
    	ElemType Data[MAXSIZE+1];//静态顺序表的数据域，这里Data[0]为空闲或者为哨兵单元 
    	int length;//顺序表的长度 
    }SqList;//顺序表 
    
    void InitList(SqList &L)//顺序表的初始化 
    { 
    	L.length = 0;//使顺序表长度归0，便是顺序表的初始化 
    }
    
    void CreateList(SqList &L)//顺序表的创建 
    { 
    	printf("请输入："); 
    	while(1)//建立一个死循环，循环终止条件是按了enter键 
    	{ 
    		L.length++;//顺序表长度加一 
    		if(L.length>MAXSIZE)//判断是否超出最大容纳量 
    		{ 
    			printf("顺序表已满！\n");
    			return ;
    		}
    		scanf("%d",&L.Data[L.length].key);//顺序表数据的输入 
    		if(getchar() == '\n')//循环终止条件 
    			break;
    	}
    }
    
    void InputList(SqList L)//顺序表的输出 
    { 
    	int i;//记录次数 
    	if(L.length == 0)//判断顺序表是否为空 ，若为空结束该函数 
    	{ 
    		printf("顺序表是空的！\n");
    		return ;
    	}
    	printf("打印为：");
    	for(i=1;i<=L.length;i++)//利用循环打印顺序表中的数据 
    		printf("%d ",L.Data[i].key);	
    }
    
    void InsertSort(SqList &L)//直接插入排序 
    { 
    	int i,j;//i表示为轮到第i个数据插入，j表示为第i个数据插入的地址 
    	for(i=2;i<=L.length;i++)//利用循环逐个插入 
    	{ 
    		if(L.Data[i].key<L.Data[i-1].key)//判断第i个和i-1个数据的大小，若小于，需将Data[i]插入有序子表中 
    		{ 
    			L.Data[0] = L.Data[i];//将待插入的记录在监视哨中 
    			L.Data[i] = L.Data[i-1];//Data[i-1]后移 
    			for(j=i-2;L.Data[0].key<L.Data[j].key;j--)//从后往前寻找插入位置 
    				L.Data[j+1] = L.Data[j];//记录逐个后移，直到找到插入位置 
    			L.Data[j+1] = L.Data[0];//将Data[0]即Data[i],插入到正确位置 
    		}
    	}
    }
    
    int main()
    { 
    	SqList L;
    	InitList(L);//初始化顺序表 
    	CreateList(L);//创建顺序表 
    	InsertSort(L);//直接插入排序 
    	InputList(L);//打印排序后结果 
    	return 0;
    }

![在这里插入图片描述][20201119161654878.png_pic_center]  
（完）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/8f781b4b9e5a4a31aeab09a68965c727.png
[20201119161654878.png_pic_center]: /images/20221120/caeec986141646fb94827bf0bf6db5a1.png