折半插入排序 C语言

蔚落 2022-12-22 09:47 165阅读 0赞

### 折半插入排序 C语言 ###

直接插入排序采用顺序查找法查找当前记录在已排好序的序列中的插入位置，这个“查找”操作可利用“折半查找”来实现，由此进行的插人排序称之为折半插入排序( Binary Insertion Sort )。

**算法步骤：**

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

![在这里插入图片描述][20201119170031296.jpg_pic_center]

**时间复杂度**  
最好情况：O(n l o g 2 log\_2 log2n)  
最坏情况：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 BInsertSort(SqList &L)//对顺序表L做折半插入排序 
    { 
    	int i,j,//i和j为数据位置 
    		low,high,mid;//low、mid、high已排序的数列中最小、中间、最大的数据位置 
    	for(i=2;i<=L.length;i++)//利用循环逐个插入 
    	{ 
    		L.Data[0] = L.Data[i];//将待插入的记录在监视哨中 
    		low = 1;
    		high = i-1;//置查找区间初值 
    		while(low<=high)//在Data[low…high]中折半查找插入的位置 
    		{ 
    			mid = (low+high)/2;//折半 
    			if(L.Data[0].key < L.Data[mid].key)
    				high = mid-1;//插入点在前一子表 
    			else
    				low = mid+1;//插入点在后一子表 
    		}
    		for(j=i-1;j>=high+1;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);//创建顺序表 
    	BInsertSort(L);//折半插入排序 
    	InputList(L);//打印排序后结果 
    	return 0;
    }

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

[20201119170031296.jpg_pic_center]: /images/20221120/97f3500a1fbd48c0964e12f61e26dd6f.png
[20201119170235484.png_pic_center]: /images/20221120/d4dd3ba0b470407aa642c07119453841.png