折半排序问题 C语言

来源：百度知道 编辑：UC知道 时间：2024/06/17 08:01:03
输入：数列中元素个数（元素数量<=100）
数列
输出：使用折半插入排序后的有序升序数列
在折半插入排序过程中进行关键字比较的次数
如输入：6
10 90 80 30 20 15
应该输出：10
4

一下是我写的程序，不知道哪里错了，请高手帮我看一下~

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

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

for (i = 0;i < m;i++)
printf ("%d ",b[i]);
printf ("\b\n%d\n",count);
getch();
}
compare (a,b,count,con,m,j)

修改好了。
你的主要错误是一个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 (