Manchester- 排序(折半插入排序）

解题思路:

折半插入排序：通过折半查找，找到插入元素在有序表中的插入位置，然后把该元素插入有序表中

①：建立一张空的顺序表

②：用折半查找法找到插入位置

1):定义Low：指向有序表第一个元素

2):定义High：指向有序表最后一个元素

3):定义mid=(Low+High)/2：指向中间元素

4):设有序表为data[100]，插入元素为x

5):如果x<data[mid],则High=mid-1

6):如果x>data[mid],则Low=mid+1

7):如果x==data[mid],则返回mid，作为插入位置

8):直到Low>High时结束循环内容：5)6)7）

9):若没找到则也要返回插入位置，此时返回插入位置Low

③：从有序表中，最后一个元素开始依次后移，直到插入位置结束

④：插入元素，同时有序表长度加1

⑤：输出结果

参考代码:

#include<stdio.h>

typedef struct List_{

 int data[100];
 int length;

}*list_,LIST;

void init_(list_ L);/*初始化顺序表*/
int half_search(list_ L,int x);
void insert_sort(list_ L,int x);
void out_put(list_ L);

int main()
{
  int x,n;/*输入的数,以及数的个数*/
  LIST L;

    while(scanf("%d",&n)!=EOF)
     {
           init_(&L);
           for(int i=0;i<n;i++)
             {
                scanf("%d",&x);
                insert_sort(&L,x);
             }
      out_put(&L);

     }
return 0;
}

/*----------------------------------------*/
void init_(list_ L)/*初始化顺序表*/
{
  L->length=0;
}
/*----------------------------------------*/
void insert_sort(list_ L,int x)
{

   int d=half_search(L,x);

     for(int i=L->length-1;i>=d;i--)
      {
         L->data[i+1]=L->data[i];
      }

       L->data[d]=x;
       L->length++;/*顺序表长度加一*/
return ;
}
/*----------------------------------------*/
int half_search(list_ L,int x)
{
    int Low=0, High=L->length-1, mid;/*让Low，High分别指向链表的左右两端*/
      while(Low<=High)
       {    mid=(Low+High)/2;
            if(x<L->data[mid])
              High=mid-1;
              else
              if(x>L->data[mid])
               Low=mid+1;
               else
               return mid;/*找到与它相同的直接返回*/
       }
       return Low;
}
/*----------------------------------------*/
void out_put(list_ L)
{
   for(int i=0;i<L->length-1;i++)
    printf("%d ",L->data[i]);

     printf("%d\n",L->data[L->length-1]);

}

别忘点赞哦-.-