插入排序算法

65 阅读 0 评论 43 点赞

我是靠谱客的博主勤奋西装，最近开发中收集的这篇文章主要介绍插入排序算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

插入排序分为三种：直接插入排序，折半插入和希尔排序算法，下面是三种排序算法的代码，代码中带有注释

直接插入排序

//直接插入排序 
void InsertSort(SqList &L)//对顺序表L做直接插入排序
{
    for(int i=2;i<=L.length;i++)
        if(L.r[i].key<L.r[i-1].key)//"<",需将r[i]存入有序字表
        {
            L.r[0]=L.r[i];//将待插入的记录暂存到监视哨中
            L.r[i]=L.r[i-1];//r[i-1]后移
            int j; 
            for(j=i-2;L.r[0].key<L.r[j].key;--j)//从后向前寻找插入位置
            L.r[j+1]=L.r[j];//记录逐个后移，直到找到插入位置
            L.r[j+1]=L.r[0];//将r[0]即原r[i],正确位置插入到
        }//if
}
//功能实现函数直接插入排序 
void Insert_sort(SqList L,int n)
{
    L.length=n;
    for(int i=1;i<=L.length;i++)
        printf("%d ",L.r[i].key);
    printf("n");
    InsertSort(L);
    for(int i=1;i<=L.length;i++)
        printf("%d ",L.r[i].key); 
}

折半插入排序

//折半插入排序
void BInsertSort(SqList &L)
{//对顺序表L做折半半插入排序 
    int i,j,low,high,mid;
	for(i=2;i<L.length;++i)
	{
		L.r[0]=L.r[i];//将待插入的记录暂存到监视哨中 
		low=1;
		high=i-1;//置查找区间初值 
		while(low<=high)//在r[low.high]中折半查找插入的位置 
		{
			mid=(low+high)/2;//折半 
			if(L.r[0].key<L.r[mid].key)//插入点在左边 
			  high=mid-1;
			else
			  low=low+1;//插入点在右边 
		}
		for(j=i-1;j>=high+1;--j)//记录后移 
			L.r[j+1]=L.r[j];
		L.r[high+1]=L.r[0];//插入到正确位置 
	}
}
//功能实现函数折半插入排序

void BInsert_Sort(SqList L,int n)
{
    L.length=n;
    for(int i=1;i<=L.length;i++)
        printf("%d ",L.r[i].key);
    printf("n");
    BInsertSort(L);
    for(int i=1;i<=L.length;i++)
        printf("%d ",L.r[i].key); 
}

下面是完整代码

//Author gyh
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXSIZE 20//顺序表的最大长度
typedef int KeyType;//定义关键字类型为整型
typedef int InfoType;
typedef struct
{
    KeyType key;//关键字项
    InfoType otherinfo;//其他数据项
}RedType;
typedef struct
{
    RedType r[MAXSIZE+1];//r[0]闲置或做哨兵单元
    int length;//顺序表的长度
}SqList;//顺序表类型
 
//直接插入排序 
void InsertSort(SqList &L)//对顺序表L做直接插入排序
{
    for(int i=2;i<=L.length;i++)
        if(L.r[i].key<L.r[i-1].key)//"<",需将r[i]存入有序字表
        {
            L.r[0]=L.r[i];//将待插入的记录暂存到监视哨中
            L.r[i]=L.r[i-1];//r[i-1]后移
            int j; 
            for(j=i-2;L.r[0].key<L.r[j].key;--j)//从后向前寻找插入位置
            L.r[j+1]=L.r[j];//记录逐个后移，直到找到插入位置
            L.r[j+1]=L.r[0];//将r[0]即原r[i],正确位置插入到
        }//if
}

//折半插入排序
void BInsertSort(SqList &L)
{//对顺序表L做折半半插入排序 
    int i,j,low,high,mid;
	for(i=2;i<L.length;++i)
	{
		L.r[0]=L.r[i];//将待插入的记录暂存到监视哨中 
		low=1;
		high=i-1;//置查找区间初值 
		while(low<=high)//在r[low.high]中折半查找插入的位置 
		{
			mid=(low+high)/2;//折半 
			if(L.r[0].key<L.r[mid].key)//插入点在左边 
			  high=mid-1;
			else
			  low=low+1;//插入点在右边 
		}
		for(j=i-1;j>=high+1;--j)//记录后移 
			L.r[j+1]=L.r[j];
		L.r[high+1]=L.r[0];//插入到正确位置 
	}
}

//希尔排序
void ShellInsert(SqList &L,int dk)
{//对顺序表L做一趟增量是dk的希尔插入排序
   int i,j;
   for(i=dk+1;i<=L.length;++i)
   {
   	 if(L.r[i].key<L.r[i-dk].key)//需将L.r[i]插入有序增量表 
   	 {
   	 	L.r[0]=L.r[i];//暂存在L.r[0]
		for(j=i-dk;j>0 && L.r[0].key<L.r[j].key;j-=dk)
			L.r[j+dk]=L.r[j];//记录后移，直到找到插入位置 
		L.r[j+dk]=L.r[0];//将r[0]即原r[i]，插入正确位置 
	 }
   } 
}
void ShellSort(SqList &L,int dt[],int t)
{
	int k;
	for(k=0;k<t;++k)
	{
		ShellInsert(L,dt[k]);
	}
}
//功能实现函数直接插入排序 
void Insert_sort(SqList L,int n)
{
    L.length=n;
    for(int i=1;i<=L.length;i++)
        printf("%d ",L.r[i].key);
    printf("n");
    InsertSort(L);
    for(int i=1;i<=L.length;i++)
        printf("%d ",L.r[i].key); 
}
//功能实现函数折半插入排序

void BInsert_Sort(SqList L,int n)
{
    L.length=n;
    for(int i=1;i<=L.length;i++)
        printf("%d ",L.r[i].key);
    printf("n");
    BInsertSort(L);
    for(int i=1;i<=L.length;i++)
        printf("%d ",L.r[i].key); 
}

//功能实现希尔排序
void Shell_Insert(SqList L,int n)
{
	int dt[3]={5,3,1};
	int t=3;
	L.length=n;
    for(int i=1;i<=L.length;i++)
        printf("%d ",L.r[i].key);
    printf("n");
    ShellSort(L,dt,t);
    for(int i=1;i<=L.length;i++)
        printf("%d ",L.r[i].key); 
}
//主函数 
int main()
{
    SqList L;
    int choice,n;
    cout<<"请输入数据个数:"<<endl;
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&L.r[i].key);
    cout<<"请输入你的插入选择方法: "<<endl;
    cin>>choice;
    switch(choice){
    	case 1:cout<<"直接插入排序为："<<endl;Insert_sort(L,n);//直接插入 
		       break;
		case 2:cout<<"折半插入排序为："<<endl;Insert_sort(L,n);//折半查找
		       break; 
		case 3:cout<<"希尔排序为: "<<endl;Shell_Insert(L,n);//希尔排序 
    }
    return 0;
}