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;
}