Manchester- 折半插入排序

解题思路:

为了便于理解，这里的代码和题目不一样

题目是在输入后的顺序表进行自身的折半插入排序

这里把过程拆开了：总思路是每输入一个元素，就在有序表里面用二分查找查找插入位置，之后直接插入到有序表里面，最后输出结果，起初有序表为空

1）：有序表的定义

typedef struct List_{
   int *Data;
   int length; /*有序表的实际长度，不是大小*/
}*List,LIST;

2）：进行有序表初始化

void initi_(List L,int n)/*初始化有序表*/
{
  L->Data=(int *)malloc(n*sizeof(int));
  L->length=0;/*有序表初始长度为0*/
}

3）：用二分查找法查找插入位置，查找元素为key，返回为插入位置的下标

int Halfsreach(List L,int key) /*折半查找插入位置*/
{
   int Low=0,High=L->length-1;
   int Mid;
    while(Low<=High)  /*在Low，High之间查找*/
     {
         Mid=(Low+High)/2;/*求中间元素位置*/
           if(L->Data[Mid]==key)
            return Mid;
            else
            if(key<L->Data[Mid])
              High=Mid-1;
              else
              Low=Mid+1;
     }
return Low;/*没找到时，返回的插入位置为Low*/
}

4）：把元素插入到有序表中，address为插入的位置即下标

void Insert_sort(List L,int key,int address) /*插入元素*/
{
    for(int i=L->length-1;i>=address;i--)/*从最后一个元素到插入位置的元素，全部后移*/
     {
        L->Data[i+1]=L->Data[i];
     }
    L->Data[address]=key;/*插入元素*/
    L->length++;/*有序表长度加1*/
}

参考代码:

#include<stdio.h>
#include<malloc.h>

typedef struct List_{
   int *Data;
   int length;
}*List,LIST;

void initi_(List L,int n);
int Halfsreach(List L,int key);
void Insert_sort(List L,int key,int address);
void print_(List L);
/*---------------------------------------------------------*/
int main()
{

  int n,key,address;
  LIST L;
    while(scanf("%d",&n)!=EOF)
     {
        initi_(&L,n);

        for(int i=0;i<n;i++)
         {
             scanf("%d",&key); /*输入元素*/
             address=Halfsreach(&L,key);/*查找位置*/
             Insert_sort(&L,key,address);/*插入元素*/
         }
     print_(&L);/*输出有序序列*/
     free(L.Data);/*释放空间*/
     }
return 0;
}
/*---------------------------------------------------------*/
void initi_(List L,int n)/*初始化有序表*/
{
  L->Data=(int *)malloc(n*sizeof(int));
  L->length=0;/*有序表初始长度为0*/
}
/*---------------------------------------------------------*/
int Halfsreach(List L,int key) /*折半查找插入位置*/
{
   int Low=0,High=L->length-1;
   int Mid;
    while(Low<=High)  /*在Low，High之间查找*/
     {
         Mid=(Low+High)/2;/*求中间元素位置*/
           if(L->Data[Mid]==key)
            return Mid;
            else
            if(key<L->Data[Mid])
              High=Mid-1;
              else
              Low=Mid+1;
     }
return Low;/*没找到时，返回的插入位置为Low*/
}
/*---------------------------------------------------------*/
void Insert_sort(List L,int key,int address) /*插入元素*/
{
    for(int i=L->length-1;i>=address;i--)/*从最后一个元素到插入位置的元素，全部后移*/
     {
        L->Data[i+1]=L->Data[i];
     }
    L->Data[address]=key;/*插入元素*/
    L->length++;/*有序表长度加1*/
}
/*---------------------------------------------------------*/
void print_(List L)
{
   for(int i=0;i<L->length-1;i++)
     printf("%d ",L->Data[i]);
     printf("%d\n",L->Data[L->length-1]);
}

别忘点赞哦-.-