数据结构之排序（直接插入排序、折半插入排序、希尔排序）

以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，实现直接插入排序，折半插入排序 和希尔排序。

#include "stdio.h"
#define MAX 100

typedef int KeyType;
typedef char InfoType[10]; 
typedef struct
{
    KeyType key;
    InfoType data;
}RecType;

//直接按照递增有序排列
void Straight_Insert_sort(RecType R[],int n)
{
    int i,j,k;
    RecType temp;
    for(i=1;i<n;i++)
    {
        temp=R[i];//设立哨兵
        j=i-1;
        while(j>=0&&temp.key <R[j].key )
        {
            R[j+1]=R[j];
            j--;
        }
        R[j+1]=temp;
        printf("i=%d,",i);
        printf("插入%3d的结果为：",temp);
        for(k=0;k<n;k++)
           printf(" %3d ",R[k].key );
        printf("\n");
    }
}

//折半插入排序
void Binary_Insert_sort(RecType R[],int n)
{
    int i,j,k,low,mid,high;
    RecType temp;
    for(i=1;i<n;i++)
    {
            
            temp=R[i];
            low=0;high=i-1;
            printf("\n第%d次要插入的关键字为：%d",i,temp);
            while(low<=high)
            {    
                mid=(low+high)/2;
                printf("\nlow=%2d ,high=%2d ,mid=%2d R[%d]=%d ",low,high,mid,mid,R[mid].key );
                if(temp.key <R[mid].key )
                    high=mid-1;
                else low=mid+1;
            
            }
            
            for(j=i-1;j>high;j--)
                R[j+1]=R[j];
            R[high+1]=temp;
        printf("\n");
    
        printf("第%d次插入后的结果为：",i);
            for(k=0;k<n;k++)
            {
            
                printf("%3d ",R[k].key );
            }
            printf("\n");
    
    }
}

//希尔排序
void ShellInsert(RecType R[],int n,int dk)
{
    RecType temp;
    for(int i=dk;i<n;i++)

        {
            temp =R[i];
        
        for(int j=i-dk;j>=0&&temp.key  <R[j].key ;j=j-dk)
            R[j+dk]=R[j];
        R[j+dk]=temp;
        }
}

void main()
{
    int i,k,n=10;
    int a[]={256,301,751,129,937,863,742,694,76,436};
    RecType R[MAX];
    for(i=0;i<n;i++)
        R[i].key =a[i];
    printf("\n\n         初始关键字: ");
    for(k=0;k<n;k++)
        printf(" %3d ",R[k].key );
    printf("\n\n");
    Straight_Insert_sort(R,n);
    printf("\n         最后结果为: ");
    for(k=0;k<n;k++)
        printf(" %3d ",R[k].key );
    printf("\n");


    for(i=0;i<n;i++)
        R[i].key =a[i];
    printf("\n 初始关键字:   ");
    for(i=0;i<n;i++)
        printf(" %3d",R[i].key );

    printf("\n");
    Binary_Insert_sort(R,n);
    printf("\n");
    printf("最后结果:\n   ");
    for(i=0;i<n;i++)
        printf("R[%d] ",i);
    printf("\n   ");
    for(i=0;i<n;i++)
        printf(" %d ",R[i]);
    printf("\n");

    for(i=0;i<n;i++)
        R[i].key =a[i];
    
    
    printf("\n 初始关键字:   ");
    for(i=0;i<n;i++)
        printf(" %3d",R[i].key );

    printf("\n");

    ShellInsert(R,n,5);
    printf("\n第一趟希尔排序的结果：\n   ");
    
    for(i=0;i<n;i++)
        printf("R[%d] ",i);
    printf("\n   ");
    for(i=0;i<n;i++)
        printf(" %d ",R[i]);
    printf("\n\n");
    
    printf("第二趟希尔排序的结果：\n   ");
    ShellInsert(R,n,3);
        for(i=0;i<n;i++)
        printf("R[%d] ",i);
    printf("\n   ");
    for(i=0;i<n;i++)
        printf(" %d ",R[i]);
    printf("\n\n");
    printf("第三趟希尔排序的结果：\n   ");
    for(i=0;i<n;i++)
        printf("R[%d] ",i);
    printf("\n   ");
    ShellInsert(R,n,1);
     for(i=0;i<n;i++)
        printf(" %d ",R[i]);
    printf("\n\n");
    printf("最后结果为：\n   ");
    for(i=0;i<n;i++)
        printf("R[%d] ",i);
    printf("\n   ");
     for(i=0;i<n;i++)
        printf(" %d ",R[i]);
    printf("\n\n");

}