数据结构实验四折半插入排序

#include "stdio.h"

#include "malloc.h"

#define maxlen 50

typedef struct

{

int data[maxlen+1];

int last;

}Sequenlist;

Sequenlist *Sqlset()

{

Sequenlist *L;

int i;

L=malloc(sizeof(Sequenlist)); L->last=0;

printf("请输入表长:\n");

scanf("%d",&i);

printf("请输入数值:\n");

if(i>0)

{

for(L->last=1;L->last<=i;L->last++) scanf("%d",&L->data[L->last]); L->last--;

}

return (L);

}

middlesort(Sequenlist *L)

{

int i,j,low,high,mid;

for(i=1;i<=L->last;i++)

{

L->data[0]=L->data[i];

low=1;

high=i-1;

while(low<=high)

{

mid=(low+high)/2;

if(L->data[0]<L->data[mid])

high=mid-1; //插入点在前半区 else

low=mid+1; //插入点在后半区 }

for(j=i;j>high+1;j--)

{L->data[j]=L->data[j-1];} //后移

L->data[high+1]=L->data[0]; //插入

}

//return(L);

}

void main()

{

Sequenlist *L;

int i;

L=Sqlset();

for(i=1;i<=L->last;i++) printf("%4d",L->data[i]); printf("\n");

middlesort(L);

printf("排序后的数据："); for(i=1;i<=L->last;i++) printf("%4d",L->data[i]); printf("\n");

}