插入排序算法：直接排序与折半排序

/*折半插入排序*/
void  B_Insert_Sort(Sqlist &L)
{
    int  i, j, low, mid, high;
    for (i = 2; i <= L.length; i++)
    {
        L.R[0] = L.R[i];
        low = 1; high = i - 1;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (L.R[0].key<L.R[mid].key)
            {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }//查找出应该插入的位置
        for (j = i - 1; j>=high+1; j--)
        {
            L.R[j + 1] = L.R[j];
        }
        L.R[high + 1] = L.R[0];
    }
}




与上述同理，循环插入第二个数开始之后的关键字。

不同的地方是，这里利用折半查找，找到，插入记录的位置，需要注意的是，为什么high+1就是应该插入关键字的位置呢？

我们可以这样想：while的最后，一定会出现low=high的情况，此时，如果哨兵的值小于mid，那么high=mid-1，实际上，mid前面值都比哨兵小，后面的值都比哨兵大，所以此时哨兵应该就在mid的位置。同理，可以得知当哨兵的值大于mid时。



完整代码：

// sort_solution.cpp: 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "stdlib.h"
#include  "malloc.h"
#define  TRUE   1
#define  ERROR  -1
#define  OVERFLOW  -2
#define  Max_Size   200
typedef  int  KeyType;
typedef  struct
{
    KeyType   key;//关键字类型
    //int     Rec;//记录类型
}RecType;
typedef  struct Sqlist
{
    int  length;
    RecType   R[Max_Size];//这里没有加一的原因是，我的length远远小于我的Max_Size
}Sqlist;//表类型
void  Create(Sqlist &L)
{
    L.length = 10;//默认表记录长度
    L.R[0].key = 0;
    for (int i=1 ;i<=L.length;i++)
    {
        printf("请输入第%d条记录的关键字：",i);
        scanf("%d",&L.R[i].key);
        getchar();
    }
}
void  Travel(Sqlist L)
{
    for (int i = 1; i <= L.length; i++)

    {
        printf("%d\r\n",L.R[i].key);
    }
}
/*直接插入排序*/
void  Straight_Insert_Sort(Sqlist  &L)
{
    int j;
    for (int i = 2; i <= L.length; i++)
    {
        L.R[0] = L.R[i];
        for (j = i - 1; L.R[j].key > L.R[0].key; j--)
        {
            L.R[j + 1] = L.R[j];
        }
        L.R[j + 1] = L.R[0];
    }
}
/*折半插入排序*/
void  B_Insert_Sort(Sqlist &L)
{
    int  i, j, low, mid, high;
    for (i = 2; i <= L.length; i++)
    {
        L.R[0] = L.R[i];
        low = 1; high = i - 1;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (L.R[0].key<L.R[mid].key)
            {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }//查找出应该插入的位置
        for (j = i - 1; j>=high+1; j--)
        {
            L.R[j + 1] = L.R[j];
        }
        L.R[high + 1] = L.R[0];
    }
}
int main()
{
    Sqlist  L;
    Create(L);
    //Straight_Insert_Sort(L);
    B_Insert_Sort(L);
    Travel(L);
    return 0;
}