直接插入排序与折半插入排序

——天道酬勤

直接插入排序的算法思路：

（1） 设置监视哨r[0]，将待插入记录的值赋值给r[0]；

（2） 设置开始查找的位置j；

（3） 在数组中进行搜索，搜索中将第j个记录后移，直至r[0].key≥r[j].key为止；

（4） 将r[0]插入r[j+1]的位置上。

折半插入排序的算法思想：

算法的基本过程：

（1）计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半；

（2）在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 .......快速的确定出第 i 个元素要插在什么地方；

（3）确定位置之后，将整个序列后移，并将元素插入到相应位置。

直接插入排序c代码如下：

#include<stdlib.h>
#include<time.h>
#include<iostream>
using namespace std;
#define num 10 
#define scope 100
void initarray(int *s)            //数组初始化，利用srand和rand生成伪随机数
{
  srand((unsigned)time(NULL));
  for(int i=1;i<=num;i++)
  {
    s[i]=rand()%scope;
  }
}
void insertsorted(int *s,int len)
{
int i,j;
for(i=2;i<=len;i++)
{
 s[0]=s[i];      //监视哨
 for(j=1;j<i;j++)
 {
   if(s[0]<s[j])
{
 for(int k=i;k>j;k--)  //数据后移，空出插入位置
 {
   s[k]=s[k-1];
 }
 s[j]=s[0];
 break;
}
 }
}
}
void show(int *s,int len)
{
  for(int i=1;i<=len;i++)
  {
    cout<<s[i]<<' ';
if(i%10==0)
{
 cout<<endl;
}
  } 
}
int main()
{
  int s[num+1];
  initarray(s);
  insertsorted(s,num);
  show(s,num);
  system("pause");
  return 0;

}

折半插入排序：

void midinsorted(int *s,int len)
{
int i,j;
int low,mid,high;
for(i=2;i<=len;i++)
{
s[0]=s[i];
low=1;
high=i-1;
for(j=1;j<i;j++)
{
 mid=(high+low)/2;
 if(s[0]<s[mid])
 {
  high=mid-1;
 }
 else
 {
  low=mid+1;
 }
 if(low>high)
 {
  for(int k=i;k>mid;k--)
  {
    s[k]=s[k-1];
}
s[low]=s[0];
 }
}
}
}