我想用循环体和函数递归调用编一个折半插入排序的程序，每循环一次插入一个数，函数递归一次可确定一个折半插入的位置及剩余的元素个数，并且能带回比较次数
语文8好` 说不清楚~举个例子吧
原序列32 13 20 40 10 30
32 比较次数为 0
13 与32比较 次数 1 新序列 13 32
20 与 13 32 中间元素13比较，20大，从子序列32中插入，再比较一次 次数2 新序列 13 20 32
就这样子

我想把新序列和原序列分别放在两个数组中，通过函数递归带回应插入的位置，然后插入，但不知道函数参数怎样设置才行`~ 那位大侠帮帮忙~ 谢了

没明白你的意思．

可用 调用函数

#define listNum 100 //定义序列长度


main()
{
int *olist; //存放源序列
int *nlist; //存放新序列

//源序列输入

binaryInsert(nlist,olist,0);
}

void binayInsert(int *nlist,int *olist,num)
{
int *account=0;
if (num<listNum)
{
newIdx=binarySearch(nlist,0,num,olist[num],account); //二分查找在nlist中olist[num]插入的位置
//在nlist的newIdx位置插入元素olist[num]
binaryInsert(nlist,olist,++num);
} else {
return 0;
}
}

int binarySearch(nlist,sIdx,eIdx,n,account)
{
//递归调用时,account都+1，最后可得到二分查找的比较次数
int mIdx=(sIdx+eIdx)/2;
if (sIdx<eIdx)
{
(*account)++;
if (n<nlist[mIdx])
{
return binarySearch(nlist,sIdx,mIdx-1,n,account);
} else if(n>nlist[mIdx]) {
return binarySearch(nlist,mIdx+1,eIdx,n,account);
} else {
return mIdx;
}
} else {
return sIdx;
}
}

由于没调试过，可能存在细节上的错误，但大致思路就是如上

另外，个人认为，插入排序的时间复杂度主要是在插入时的数组移动阶段，其整个时间复杂度是o(n^2)，
即使你在搜索位置时用了折半查找也不能降低其时间复杂度。而用折半查找，你的代码可读性就要比顺序查找插入位置的代码的可读性降低了。

[此贴子已经被作者于2007-1-2 12:49:09编辑过]