i

来自「1、猴子选大王 2、约瑟夫环 3、迷宫求解 4、回文游戏 5、地图四染色」· 代码 · 共 46 行

//折半插入排序

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#define n 10

int r[n+1];

void BInsertSort()
{
    //折半插入排序 
    int i,j,low,high,m;
    for(i=1;i<=n;++i) 
    {
        r[0]=r[i];
        low=1;high=i-1;
        while(low<=high)
        {
                m=(low+high)/2;    //折半 
                if(r[0]<=r[m])high=m-1;//插入点在低半区 
                else low=m+1;//插入点在高半区 
        }// while
        for(j=i-1;j>=high+1;--j)
                r[j+1]=r[j];
        r[high+1]=r[0];
    }
}

int main(int argc, char *argv[])
{
  int k,i,j;
  r[0]=0;
  for(k=1;k<=n;k++)
     {r[k]=n-k+1;printf("%d  ",r[k]);}
  BInsertSort(); 
  for(k=1;k<=n;k++)
     {printf("%d  ",r[k]);}
  system("PAUSE");	
  return 0;
}