c语言实现折半排序算法

㈠ 一C程序 数据结构综合实验 折半插入排序算法的实现与分析

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef int KeyType;
typedef int DataType;
typedef struct{
KeyType key;
//DataType data;
}SortItem,SqList[MAXSIZE];
int bubblesort(SqList L,int n);
int BiInsertSort(SqList L,int n);
int main()
{
int m,n,i,j,k;
SqList L;
scanf("%d",&n);
srand(0);
for(i=0;i<n;i++) L[i].key=rand()%1000;
k=BiInsertSort(L,n);
for(i=0;i<n;i++) {if(i==10) printf("\n%d ",L[i]); else printf("%d\n",L[i]);}
printf("\n\n%d",k);
system("pause");
return 0;
}

int bubblesort(SqList L,int n)
{
int i,j,over,count=0;
SortItem p;
for(i=0;i<n-1;i++)
{
over=1;
count++;
for(j=n-1;j>i;j--)
{

if( count++&&L[j].key<L[j-1].key)
{
p=L[j];
L[j]=L[j-1];
L[j-1]=p;

over=0;
count++;
}

}
if(over) break;
}

return count+1;
}

int BiInsertSort(SqList L,int n)
{
int i,j,low,upper,mid;
SortItem p;
for(i=1;i<n;i++)
{
p=L[i];
low=0;
upper=i-1;
while(low<=upper)
{
mid=(low+upper)/2;
if(p.key<L[mid].key) upper=mid-1;
else low=mid+1;
}
for(j=i-1;j>=low;j--) L[j+1]=L[j];
L[low]=p;

}

return 0;

}

㈡ 请写一个折半插入排序算法（最好用C语言写出来，只要求写一个函数）

/***折半插入排序***/
/*算法原理：从第二个数开始逐个置入监视哨，使用low，high标签在L[0..i-1]有序区内进行折半查找
来确认待排序数的插入位置，然后将该位置到最后一个数全部后移一位，最后腾出该位置，
把监视哨里面的数置入该位置。后面的数以此类推进行排序，直到最后一个数比较完毕。
*/
#include<stdio.h>
voidbinaryInsertSort(intL[],intn)
{
	inti,j;
	intlow,high,mid;
	//用L[0]作为监视哨，L[1..i-1]为有序区，
	for(i=2;i<=n;i++)
	{
		L[0]=L[i];		//待排序的数进监视哨
		low=1;
		high=i-1;		//初始化low，high
		while(low<=high)//循环语句确定插入位置，必须保证low<=high
		{
			mid=(low+high)/2;
			if(L[0]<L[mid])//根据L[0]的值的大小,确定属于低半区还是高半区
				high=mid-1;//插入低半区//插入低半区
			else
				low=mid+1;//插入高半区
		}
		for(j=i-1;j>=high+1;j--)//待插入位置后面L[hign+1..i-1]全部数后移一位
			L[j+1]=L[j];
		L[high+1]=L[0];		//或者换成L[j+1]=L[0];监视哨里面的数插入数组
	}
}

voidbinaryInsertSort1(intL[],intn)
{
	inti,j;
	intlow,high,mid,tmp;
	//用临时变量tmp作为监视哨，L[0..i-1]为有序区
	for(i=1;i<n;i++)
	{
		tmp=L[i];
		low=0;
		high=i-1;
		while(low<=high)
		{
			mid=(low+high)/2;
			if(tmp<L[mid])
				high=mid-1;
			else
				low=mid+1;
		}
		for(j=i-1;j>=high+1;j--)
			L[j+1]=L[j];
		L[high+1]=tmp;
	}
}

intmain()
{
	inti,n;
	inta[50];
	printf("输入n=");
	scanf("%d",&n);
	printf("输入数组元素：
");
//	for(i=1;i<=n;i++)
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
//	binaryInsertSort(a,n);
	binaryInsertSort1(a,n-1);
	printf("排序后;
");
//	for(i=1;i<=n;i++)
	for(i=0;i<n;i++)
		printf("%-4d",a[i]);
	putchar(10);
	return0;
}