Manchester


私信TA

用户名:wenyajie

访问量:163397

签 名:

在历史前进的逻辑中前进,这个逻辑就是人心向背的逻辑

等  级
排  名 1
经  验 38320
参赛次数 1
文章发表 188
年  龄 0
在职情况 学生
学  校 Qing Dao University
专  业 计算机科学

  自我简介:

在历史前进的逻辑中前进,这个逻辑就是人心向背的逻辑

解题思路:

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


①:建立一张空的顺序表

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


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]);

}

别忘点赞哦-.-

 

0.0分

1 人评分

  评论区