折半排序演算法

1. 請寫一個折半插入排序演算法（最好用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;
}

2. c語言中的折半排序法是怎樣的，基本程序是怎樣的

折半法
應該叫做2分法。
用2分法查找數
需要先對數組進行排序（升序或降序）
假如你所要查找的數是20
數組是 1 4 7 8 20 30 34
每次都拿中間的數跟你要比的數比
也就是 8和20比
發現20比8大
所以左面的數都不要了
剩下的是 20 30 34
再拿20跟30比
發現20比30小
右面的數都不要了
再拿20跟20比
相等，則找到了。
如果找不到返回-1
下面是程序。

#include <iostream>
using namespace std;

int binarySearch(int* data,int low,int high,int value)
{

int k=(low+high)/2;

if(value<*(data+low)||value>*(data+high))
{
return -1;
}

if(value<*(data+k))
{
return binarySearch(data,low,k-1,value);
}

else if(value>*(data+k))
{
return binarySearch(data,k+1,high,value);
}

else
return k;

}

void main()
{
int pos;
int arr1[9]={1,2,3,4,5,6,7,8,9};
int i=9;
while(i)
{
pos=binarySearch(arr1,0,8,i);
cout<<"數字"<<i<<"的下標是:"<<pos<<endl;
i--;
}

pos=binarySearch(arr1,0,8,20);
cout<<"數字20的下標是:"<<pos<<endl;
}

3. 用折半插入排序方法寫出程序，完成數字12在數列（1，6，9，13，20，29）的排序工作（C語言）

解：用有序列插入法排序，過程如下：

第一步：7  1      （前兩個數7，1排成有序列）

第二步：7  3  1    （第3個數3按要求插入到已排好的有序列中）

第三步：12  7  3  1    （第4個數12按要求插入到已排好的有序列中）

第四步：12  8  7  3  1    （第5個數8按要求插入到已排好的有序列中）

第五步：12  8  7  4  3  1    （第6個數4按要求插入到已排好的有序列中）

第六步：12  9  8  7  4  3  1    （第7個數9按要求插入到已排好的有序列中）

第八步：12  10  9  8  7  4  3  1    （第8個數10按要求插入到已排好的有序列中）

這時各數的順序就是符合要求的最終順序.

用折半插入排序法，將新數據6插入到上面的有序列中，演算法步驟設計如下：

第一步：把新數據6與「中間位置」的數據8比較，由於6＜8，所以應將6放到8的右邊的一半有序列中，即應放到有序列7，4，3，1中.

第二步：把6與有序列7，4，3，1「中間位置」的數據4比較，由於4＜6，所以應將6放到4的左邊的一半有序列中，即應放到有序列7，4中.

第三步：把6與有序列7，4「中間位置」的數據7比較，由於7＞6，所以應將6放到7的右邊的一半有序列中，至此排序完成，得到一新的有序列

12，10，9，8，7，6，4，3，1