#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20
typedef struct {
int length;
int *data;
}SqSort;

void InitSort(SqSort &L); //初始化
void CreateSort(SqSort &L,int n); //排序的建立
void BinsertSort(SqSort &L); //折半插入排序
void DisplaySort(SqSort L); //将排序过后的元素进行输出

void InitSort(SqSort &L)
{
   L.data=(int *)malloc(sizeof(int)*MAXSIZE); //为L.data指针所指向的位置分配MAXSIZE的空间
   if(L.data==NULL)
   {
       printf("No enough memory to allocate!!!\n");
   }
   L.length=0;
}

void CreateSort(SqSort &L,int n)
{
   int i;
   printf("请输入%d个整数：\n",n);
   for(i=1;i<=n;i++) //0号元素作为哨兵
   {
       scanf("%d",&L.data[i]);
       L.length++;
   }
}

void DisplaySort(SqSort L)
{
   int i;
   for(i=1;i<=L.length;i++)
   {
       printf("%d ",L.data[i]);
   }
}

void BinsertSort(SqSort &L)
{
   int i,j,low,mid,high;
   for(i=2;i<=L.length;++i)
   {
       L.data[0]=L.data[i]; //将当前元素存入哨兵
       low=1,high=i-1;
       while(low<=high)
       {
           mid=(low+high)/2;
           if(L.data[0]<mid)
           {
               high=mid-1;
           }
           else
           {
               low=mid+1;
           }
       } //此时循环结束，i要插入的位置是high+1，指向的元素位置
       for(j=i-1;j>=high+1;--j)
       {
           L.data[j+1]=L.data[j]; //元素后移
       }
       L.data[high+1]=L.data[0];
   }
}

int main()
{
   SqSort L;
   int n,i;
   InitSort(L);
   printf("How many number you want to input:\n");
   scanf("%d",&n);
   CreateSort(L,n);
   printf("此数组的长度为：%d",L.length);
   BinsertSort(L);
   printf("Plese output you alread sort numbers\n");
   DisplaySort(L);
   free(L.data);
}

ljxzhuce

Viewpage+fragment遇到的疑惑

8条回答

为你推荐