insertsort.cpp

各种内部排序算法的实现和比较

#include "base.h"

void InsertSort(SqList &L)
{//对顺序表L直接插入排序
	int i,j;

	for(i=2;i<=L.length;i++)
	{
		if(LT(L.r[i].key,L.r[i-1].key))
		{
			L.r[0]=L.r[i];
			L.r[i]=L.r[i-1];
			for(j=i-2;LT(L.r[0].key,L.r[j].key);j--)
				L.r[j+1]=L.r[j];
			L.r[j+1]=L.r[0];
		}
	}
}

void BInsertSort(SqList &L)
{//对顺序表L折半插入排序
	int i,j,m;
	int low,high;

	for(i=2;i<=L.length;i++)
	{
		L.r[0]=L.r[i];
		low=1;	high=i-1;
		while(low<=high)
		{
			m=(low+high)/2;
			if(LT(L.r[0].key,L.r[m].key))
				high=m-1;
			else
				low=m+1;
		}
		for(j=i-1;j>=high+1;j--)
			L.r[j+1]=L.r[j];
		L.r[high+1]=L.r[0];
	}
}

void Arrange(SLinkListType &SL)
{//重排顺序表SL,以便于输出
	int p,q,i;
	SLNode t;
	
	p=SL.r[0].next;

	for(i=1;i<=SL.length;i++)
	{
		while(p<i)
			p=SL.r[p].next;
		q=SL.r[p].next;
		if(p!=i)
		{
			t=SL.r[i];
			SL.r[i]=SL.r[p];
			SL.r[p]=t;
			SL.r[i].next=p;
		}
		p=q;
	}
}

void SInsertSort(SLinkListType &SL)
{//对顺序表SL插入排序
	int i,p,q,x; 

	SL.r[0].next=1;
	SL.r[1].next=0;

	for(i=2;i<=SL.length;i++)
	{
		p=0;
		x=SL.r[i].rc;

		while(SL.r[SL.r[p].next].rc<x&&SL.r[p].next!=NULL)
			p=SL.r[p].next;
		q=SL.r[p].next;
		SL.r[p].next=i;
		SL.r[i].next=q;
	}
	Arrange(SL);
}

void ShellInsert(SqList &L,int dk)
{//对顺序表进行希尔插入
	int i,j;

	for(i=dk+1;i<=L.length;i++)
		if(LT(L.r[i].key,L.r[i-dk].key))
		{
			L.r[0]=L.r[i];
			for(j=i-dk;j>0&&LT(L.r[0].key,L.r[j].key);j=j-dk)
				L.r[j+dk]=L.r[j];
			L.r[j+dk]=L.r[0];
		}
}

void ShellSort(SqList &L,int dlta[],int t)
{//希尔排序
	int k;

	for(k=0;k<t;k++)
		ShellInsert(L,dlta[k]);
}

void TwoInsertSort(SqList &L)
{//二路插入排序
	int x,i,j,first,final;
	RedType *d;
	d=new RedType[L.length];

	for(i=0;i<L.length;i++)
		d[i].key=0;
	d[1]=L.r[1];
	x=L.r[1].key;
	first=final=1;

	for(i=2;i<=L.length;i++)
	{
		if(L.r[i].key>=x)
		{
			for(j=final;d[j].key>L.r[i].key;j--)
				d[j+1]=d[j];
			d[j++].key=L.r[i].key;
			final++;
		}
		else
		{
			if(first==1)
			{
				d[L.length].key=L.r[i].key;
				first=L.length;
			}
			else
			{
				for(j=first;d[j].key<L.r[i].key;j%L.length+1)
					d[i-1]=d[i];
				if(j==0)
					j=L.length;
				else
					j--;
				d[j].key=L.r[i].key;
				first--;
			}
		}
		for(i=first,j=1;j<=L.length;i=i%L.length+1,j++)
			L.r[j]=d[i];
	}
}