折半插入排序c语言

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

2. 请写一个折半插入排序算法（最好用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;
}

3. c语言 近半插入排序 急求 求各位高手指点 实在是不会啊

# include "iostream"
using namespace std;
struct Record
{
int key;
};
void BubbleSort(Record r[],int n)
{
int exchange = 1;
while(exchange)
{
exchange = 0;
for(int i = 1;i < n;i++)
for(int j = 0;j < n - i;j++)
{
if(r[j].key > r[j+1].key)
{
Record temp;
temp = r[j];
r[j] = r[j+1];
r[j+1] = temp;
exchange = 1;
}
}
}
}
void SelectSort(Record r[],int n)
{
for(int i = 0;i < n - 1;i++)
{
int k = i;
for(int j = i + 1;j < n;j++)
if(r[j].key < r[k].key)
k = j;
if(k != i)
{
Record temp;
temp = r[i];
r[i] = r[k];
r[k] = temp;
}
}
}
void InsertSort(Record r[],int n)
{
for(int i = 1;i < n;i++)
{
Record temp;
temp = r[i];
for(int j = i -1;j >= 0 && temp.key < r[j].key;j--)
r[j+1] = r[j];
r[j+1] = temp;
}
}
void BinInsertSort(Record r[],int n)
{
for (int i = 1;i < n;i++)
{
Record temp;
temp = r[i];
int low = 0;
int high = i - 1;
while(low <= high)
{
int mid = (low + high)/2;
if(temp.key < r[mid].key)
high = mid -1;
else
low = mid + 1;
}
for(int j = i - 1;j >= low;j--)
r[j+1] = r[j];
r[low] = temp;
}
}
void ShellSort(Record r[],int n)
{
for(int d=n/2;d >= 1;d=d/2)
{
for(int i = d;i < n;i++)
{
Record temp;
temp = r[i];
for (int j=i-d;j >= 0 && temp.key < r[j].key;j = j-d)
r[j+d] = r[j];
r[j+d] = temp;
}

}
}
int Partition(Record r[],int i,int j)
{
Record temp;
temp = r[i];
while(i < j)
{
while(i < j && r[j].key >= temp.key)
j--;
if(i < j)
r[i++] = r[j];
while(i < j && r[i].key <= temp.key)
i++;
if(i < j)
r[j--] = r[i];
}
r[i] = temp;
return i;

}
void QuickSort(Record r[],int i,int j)
{
if(i < j)
{
int pivot = Partition(r,i,j);
QuickSort(r,i,pivot-1);
QuickSort(r,pivot+1,j);
}
}
void Printf(Record r[],int n)
{
for(int h = 0;h < n;h++)
cout<<r[h].key<<",";
cout<<endl;
}
void main()
{
Record r[6] = {3,6,24,12,18,5};
//BubbleSort(r,6);
//SelectSort(r,6);
//InsertSort(r,6);
//BinInsertSort(r,6);
//ShellSort(r,6);
QuickSort(r,0,5);
Printf(r,6);

}其中有BinInsertSort函数就是折半插入排序

4. 数据结构实现折半插入排序(c语言版)

# include <stdio.h>#define Max 7
void B_sort(int a[], int n)
{
int low,high, i,j, t;
int m;
for(i=2;i<=n;++i)
{
t = a[i];//临时存放
low =1;high =i-1;
while(low<=high)
{
m=(low+high)/2;
if(t<a[m])
high =m-1;
else
low =m+1;
}
for(j=i-1;j>=high+1;--j)

{
a[j+1] = a[j];
}

a[high+1] = t;
}}
main()
{int a[Max],i;
int length = Max-1;
printf(" 这是一个折半排序 \n");
printf("请输入%d个待排序的记录序列:\n",length-1);
for(i=1;i<length;i++)
scanf("%d",&a[i]);
B_sort(a,length);
printf("折半排序后的序列:");
for(i=2;i<=length;i++)
printf(" %d",a[i]);
printf("\n");
}

vc下面编译通过的，折半插入排序，希望采纳

5. C语言帮我解释下折半插入排序代码

你把题目给我一下！其实你要学排序最好就学
1.冒泡排序（最简单，最慢）
2。取中快排（最快，但不稳定，不过不影响大局，最好背这个）
3.桶排序（比较快，其实也还没有2的一半，就是结构稳定）

6. C语言折半插入排序

修改好了。
你的主要错误是一个j--写成了j++. 此外，我给你加了一点检查的代码。
此外，count的值是0，你没有统计它，你自己再修改一下。

#include <stdio.h>

main()
{
int a[101],b[101],con,count = 0,i,j,t,n,m=0; /*count用来记录计算次数，a数组是输入数组，b数组时排序以后数组，con用来标记看a数组中的数字是否找到相应的位置，m用来表示b数组长度*/
scanf ("%d",&n);
for ( i = 0;i < n; i++) /*输入数据*/
scanf ("%d",&a[i]);
b[0] = a[0];
m = 1;

for (i = 1;i < n;i++)
{
j = m / 2;
con = 1;
t = compare ( a[i],&b[j],&count,&con,&m,&j); /*conpare函数用来寻找a中数字插入的位置*/
if (t == 200) { /* check abnormal return */
printf("unexpected error\n");
exit(1);
}
printf("m = %d, t = %d\n", m, t);
for (j = m;j > t;j--) /*找到位置以后重新排序*/ // j--, not j++
b[j] = b[j-1];
b[t] = a[i];
if ( t != 200)
m = m+1;
}

printf("The sorted array:\n");
for (i = 0;i < m;i++)
printf ("%d ",b[i]);
printf ("\b\ncount: %d\n",count);
printf("press any key to exit\n");
getch();
}

int
compare (a,b,count,con,m,j) /*j表示所插入的位置*/
int a,*b,*count,*con,*m,*j;
{
int i,k = 0;
if (a > *b)
{
*con = 2 * (*con); /*用整除的方式表示，能被2整除，说明有过比a小的数字，能被3整除说明比较过比a大的数字，而当a在比它比它小的数之间时，被六整除，可以得到所求的位置*/
i = 1;
*j = *j + 1;
}
if (a < *b)
{
*con = 3 * (*con);
i = -1;
*j = *j -1;
k = 1;
}
if (a == *b)
return 200; /*返回值为200说明有数字相同，重新排序操作*/
if (*con % 6 == 0 || *j == -1 || *j == *m) /*当j过大或者过小的时候把数字排列在最左边或者最右边，返回主函数*/
return (*j + k);
else return compare (a,b+i,count,con,m,j); /*当还没找到所需要位置的时候，再次使用该函数找到位置*/
}

7. 用c语言，折半插入排序10个随机数，主体插入排序，查找位置采用折半查找的方法。

教材上有写：折半插入排序基本思想和直接插入排序一样，区别在于寻找插入位置的方法不同，折半插入排序采用折半查找法来寻找插入位置。折半查找法只能对有序的序列使用。基本思想就是查找插入位置的时候，把序列分成两半（选择一个中间数mid），如果带插入数据大于mid则到右半部分序列去在进行折半查找；反之，则到左半部分序列去折半查找。
折半插入排序在记录移动次数上和直接插入排序是一样，所以算法时间复杂度也是一样，只是在寻找插入位置的时候可能会节约相当多的时间。

8. 用折半插入排序方法写出程序，完成数字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