数据结构实验+折半插入排序算法的实现

朱雀 2022-11-05 14:52 127阅读 0赞

## 折半插入排序算法的实现 ##

#include <stdio.h>
    
    //6-1存储结构
    #define MAXSIZE 20
    typedef int KeyType;
    typedef struct
    {
    	KeyType key;
    }RedType;
    typedef struct  
    {
    	RedType *r;
    	int length;
    }SqList;
    
    //6-2初始化
    void InitList(SqList &L)
    {
    	L.r=new RedType[MAXSIZE+1];
    	L.r[0].key=0;   //初始化一个哨兵
    	L.length=0;
    }
    
    //6-3折半插入排序
    void BInsertSort(SqList &L)   
    { 
    	int m,low,high;
    	for(int 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)｛
    				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;
    	int n,i;
    	//
    	InitList(L);
    	printf("请输入待排序的元素个数：");
    	scanf("%d",&n);
    	while(n>MAXSIZE || n<1)
    	{
    		printf("元素个数n超过了最大值MAXSIZE或者小于1，请重新输入：");
    		scanf("%d",&n);
    	}
    	L.length=n;
    	printf("请依次输入%d个元素：",n);
    	for (i=1;i<=L.length;i++)
    	{
    		scanf("%d",&L.r[i].key);
    	}
    	//
    	printf("待排序的记录为：");
    	for (i=1;i<=L.length;i++)
    	{
    		printf("%3d",L.r[i].key);
    	}
    	printf("\n");
    	//
    	BInsertSort(L);
    	printf("排序后的数据为：");
    	for (i=1;i<=L.length;i++)
    	{
    		printf("%3d",L.r[i].key);
    	}
    	printf("\n");
    }

![Xnip2020-12-22\_21-44-20][Xnip2020-12-22_21-44-20]

[Xnip2020-12-22_21-44-20]: /images/20221023/57605f74c2cf4fd2b771e40d8d60a283.png