技术笔试面试

折半插入排序-改进的直接插入排序

直接插入排序算法,在排序记录的数量n很小时,是一种很好的排序算法,但通常待排序列中记录数量n很大,此时就不宜使用直接插入排序了。

在直接插入排序的基础上,从减少“比较”和“移动”这两种操作的次数着眼,可得到一些改进了的插入排序的方法,比如折半插入排序。

由于插入排序的基本操作是在一个有序表中进行查找和插入,这个“查找”完全可以采用“折半查找”来实现,由此称之为“折半插入排序(Binary Insertion Sort)”。

折半插入排序源代码如下:

#include
#include
#include

void si_sort(int arr[],int arrnum)
{
int low,high;
int i,mid,j;
for(i=2;i<=arrnum-1;i++){
   arr[0]=arr[i];
   low=1;
   high=i-1;
   while(low<=high){
      mid=(low+high)/2;
      if(arr[0]=high+1;j--)
      arr[j+1]=arr[j];
   arr[high+1]=arr[0];
}
}

void print_arr(int arr[],int arrnum){
int i=1;
printf("Sorted:");
for(;i<=arrnum;i++){
printf("%d ",arr[i]);
}
}

int main()
{
int index=1,arrnum;
char s[100],*sp;
int num[10]={0};
printf("Please input(ex:3 5 6 1 7 14):");
fgets(s,sizeof(s),stdin);
sp=strtok(s," ");
while(sp!=NULL){
printf("%s",sp);
num[index++]=atoi(sp);
sp=strtok(NULL," ");
}
arrnum=index-1;
printf("%d\n",arrnum);
si_sort(num,arrnum);
print_arr(num,arrnum);
return 0;
}

over~

1条评论

  1. 该算法明显有问题,实在不敢恭维。你试过了么就放上来
    for(i=2;i<=arrnum-1;i++){
    为什么从2 开始?还有很多问题 arr[0]=arr[i];
    每次都改?

发表您的评论

请您放心,您的信息会被严格保密。必填项已标识 *