posts - 63, comments - 37, trackbacks - 0, articles - 0
  IT博客 :: 首页 :: 新随笔 :: 联系 ::  :: 管理

折半插入排序

Posted on 2006-06-13 21:46 Enjoy Life 阅读(2001) 评论(3)  编辑 收藏 引用 所属分类: DS study

void BiInsertionSort(SqList &L){
   //对顺序表L作折半插入排序
   for(i=2; i<=L.length; ++i){
      L.r[0] = L.r[i];
      low = 1;
      high = i-1;

        //查找i记录应该插入的位置,必定是high+1的位置从而high+1位置以后的元素都应该往后移动一个位置,留出一个位置放入L.r[i]
      while(low <= high){
         mid = (low + high)/2;
         if(LT(L.r[0], L.r[m].key))
            high = m - 1;
         else
            low = m + 1;
      }
      //后移
      for(j=i-1; j>=high+1; --j)
         L.r[j+1] = L.r[j];
      //插入元素
      L.r[high+1] = L.r[0];
   }
}

Feedback

# re: 折半插入排序  回复  更多评论   

2006-09-22 16:18 by 杨涛
#include <iostream.h>
#include <stdio.h>
void binsertsort(int r[] ,int n)
{
int i,j;
int low,high;
int m;

for(i=2;i<=n;i++)
r[0]=r[i]; // 将r[i]暂存到 r[0]
low=1;
high=i-1;
while(low<=high)
{
m=(low+high)/2 ;
{
if(r[0]<r[m])
high=m-1;
else low=m+1;
}
for(j=i-1;j>=high+1;j--)

r[j+1]=r[j];
r[high+1]=r[0];

}

}

void print(int r[] ,int n)
{
int i;
for(i=0;i<n;i++)
printf("r[%d]=%d\n",i,r[i]);
}
void main()
{
int i,j;
int n;

int r[100];

scanf("%d",&n);
printf("要排序的数据个数%d为",n);
for(i=0;i<n;i++)
scanf("%d",&r[i]);
printf("插入前的数组为");
print(r,n);
binsertsort(r,n);
printf("插入后的数组为");
print(r,n);


}

# re: 折半插入排序  回复  更多评论   

2009-05-05 19:20 by wangwei
运行结果不对,程序有错

# re: 折半插入排序  回复  更多评论   

2009-12-07 16:41 by savio_2002
//折半插入排序
template<typename T>
void BInsertSort(T array[],int n)
{
int i,j,mid;
int low,high;
T temp;
for (i=1;i<n;++i)
{
temp=array[i];
low=0;
high=i-1;
while (low<=high)
{
mid=(low+high)/2;
if (temp<array[mid])
{
high=mid-1;
}
else
{
low=mid+1;
}
}

for (j=i-1;j>=high+1;j--)
{
array[j+1]=array[j];
}
array[high+1]=temp;
}
}
只有注册用户登录后才能发表评论。