‘壹’ 请写一个折半插入排序算法（最好用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;
}
‘贰’ 用折半插入排序方法写出程序，完成数字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
‘叁’ 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); /*当还没找到所需要位置的时候，再次使用该函数找到位置*/
}
‘肆’ 用c语言，折半插入排序10个随机数，主体插入排序，查找位置采用折半查找的方法。
教材上有写：折半插入排序基本思想和直接插入排序一样，区别在于寻找插入位置的方法不同，折半插入排序采用折半查找法来寻找插入位置。折半查找法只能对有序的序列使用。基本思想就是查找插入位置的时候，把序列分成两半（选择一个中间数mid），如果带插入数据大于mid则到右半部分序列去在进行折半查找；反之，则到左半部分序列去折半查找。
折半插入排序在记录移动次数上和直接插入排序是一样，所以算法时间复杂度也是一样，只是在寻找插入位置的时候可能会节约相当多的时间。
‘伍’ 请写一个折半插入排序算法（最好用C语言写出来，只要求写一个函数）。
折半插入排序算法：
//创建链表
StatusEnSqList(SqList*L,ElemTypee,intn)
{
if(L->length>=n)
returnERROR;
L->data[L->length+1]=e;
L->length++;
returnOK;
}
//折半插入排序算法
voidBInsertSort(SqList*L)
{
inti,j,mid,high,low;
for(i=2;i<=L->length;i++)
{
low=1;
high=i-1;
L->data[0]=L->data[i];
while(low<=high)
{
mid=(low+high)/2;
if(L->data[0]<L->data[mid])
high=mid-1;
else
low=mid+1;
}
for(j=i-1;j>=high+1;j--)
L->data[j+1]=L->data[j];
L->data[high+1]=L->data[0];
}
}
intmain(void)
{
SqListL;
intn,i;
ElemTypee;
L.length=0;
printf("输入元素个数：");
scanf("%d",&n);
L.data=(int*)malloc(sizeof(int)*n);
printf("输入各个元素的值：");
for(i=0;i<n;i++)
{
scanf("%d",&e);
EnSqList(&L,e,n);
}
BInsertSort(&L);
for(i=1;i<=n;i++)
printf("%d",L.data[i]);
printf(" ");
return0;
}
‘陆’ c语言编程实现“折半查找”的过程。
折半查找的算法思想是将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。 折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。参考程序，希望对你有所帮助！
#include<stdio.h>
void main()
{
int a[20],x,i,start,end;
printf("input 20 numbers:\n");
for(i=0;i<20;i++) scanf("%d",&a[i]);
printf("please enter the number:\n");
scanf("%d",&x);
for(start=0,end=19;start<=end;)
{
i=start+(end-start)/2;
if (x==a[i])
{
printf("%d",i+1);
getch();
return;
}
else if (x>a[i]) end = i-1;
else start=i+1;
}
}
‘柒’ 用c语言写一个算法（折半或二分法），实现可以选择1到20的从小到大以
解：用有序列插入法排序，过程如下：
第一步：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
‘捌’ C语言 折半排序法（二分排序法）求大神补充，急需
intTwoPointsRanking(intarray[],intnum,size_tsize,intmax){
intleft=0;
intright=size-1;
intmiddle=0;
intmoveindex=0;
do{
if(size==max){
return-1;
}
if(size==0){
array[0]=num;
}else{
while(left<=right){
middle=(left+right)/2;
if(num<array[middle]){
right=middle-1;
}else{
left=middle+1;
}
}
for(moveindex=size-1;moveindex>=left;moveindex--)
{
array[moveindex+1]=array[moveindex];
}
array[left]=num;
}
}while(0);
return0;
}
#defineMAX5
intmain(intargc,char*argv[]){
intarray[MAX];
intinput=0;
size_tsize=0;
size_tindex=0;
do{
printf("输入：");
scanf("%d",&input);
if(input==0){
printf("退出
");
break;
}
if(TwoPointsRanking(array,input,size,MAX)==-1){
printf("已满
");
break;
}
size++;
for(index=0;index<size;index++)
printf("%d",array[index]);
printf("
");
}while(1);
return0;
}