例如一个数组 a[10]={0,1,2,3,4,6,7,8,9} 已排为升序,现在想将数5用二分法插入到数组a的正确地方,具体的C语言代码是什么呢?多谢了!
#include<stdio.h>
int main()
{
int n=9;//数组元素个数
int a[10]={0,1,2,3,4,6,7,8,9};
//开始两分查找
int i,j,mid,insert=5;
i=0; j=n-1;
while(i<=j){
mid=(i+j)/2;
if(a[mid]>insert)
j=mid-1;
else if(a[mid]<insert)
i=mid+1;
else//a[mid]==inset,数据重复
return 0;
}
//两分查找结束
//此时a[j]<insert<a[i],i-j=1
//把元素a[i...n-1]往后移
for(j=n;j>=i;j--)
a[j]=a[j-1];
//插入insert
a[i]=insert;
//调整元素个数
n++;
//输出
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}
其它补充:
(1)因为这是数组,数组插入元素时必须移动从插入位置往后所有的元素,所以用两分法一点也不高效。想高效地用两分法插入应该使用二叉树。
(2)高效地往已排序的数组中插入元素应该直接从后往前一边比较一边移边。
(3)程序中的两分查找非常有用,如果不会,一定要掌握。尤其要了解当跳出while循环时i,j值的含义,这样才能应对各种使用上的变化。
(4)本程序中,如果把insert改成-1或10,同样可以运行。
int main()
{
int n=9;//数组元素个数
int a[10]={0,1,2,3,4,6,7,8,9};
//开始两分查找
int i,j,mid,insert=5;
i=0; j=n-1;
while(i<=j){
mid=(i+j)/2;
if(a[mid]>insert)
j=mid-1;
else if(a[mid]<insert)
i=mid+1;
else//a[mid]==inset,数据重复
return 0;
}
//两分查找结束
//此时a[j]<insert<a[i],i-j=1
//把元素a[i...n-1]往后移
for(j=n;j>=i;j--)
a[j]=a[j-1];
//插入insert
a[i]=insert;
//调整元素个数
n++;
//输出
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}
其它补充:
(1)因为这是数组,数组插入元素时必须移动从插入位置往后所有的元素,所以用两分法一点也不高效。想高效地用两分法插入应该使用二叉树。
(2)高效地往已排序的数组中插入元素应该直接从后往前一边比较一边移边。
(3)程序中的两分查找非常有用,如果不会,一定要掌握。尤其要了解当跳出while循环时i,j值的含义,这样才能应对各种使用上的变化。
(4)本程序中,如果把insert改成-1或10,同样可以运行。
温馨提示:答案为网友推荐,仅供参考