sort.cpp

堆排,快排,希尔排序,插入排序,等多种排序方面法简介,及源程序.

//排序的相关算法
# include<stdio.h>
# include<stdlib.h>
# include<string.h>
# define maxsize 20

int a[20]={98,76,52,34,12,446,754,963,85,741,102,105,52,41,456,843,951,458,756,984};
char b[20][100]={"成也风云","多情自古","桃花依旧","天道酬勤","我命由我","海纳百川",
                  "心中无敌","自强则胜","自信则强","自立求生","直挂云帆","上善若水","梦想何方","奋斗人生",
				  "心与明月","有容乃大","花谢花开","云卷云舒","天下为公","敢笑黄巢"};


typedef struct  queue   //链队列的定义，为链式基数排序作准备
{
   keytype key;
   struct queue  *next;
}queue;
	
	typedef int keytype;

typedef struct   //定义记录结点
{
	keytype key;
	char *name;
    int next;   //为表插入排序作准备
}redtype;

typedef struct   //定义存放记录的顺序表
{
	redtype r[maxsize+1];
	int length;
}sqlist;

void Insertsort(sqlist *L)   //直接插入排序
{
	int i,j;
	for(i=2;i<=L->length;i++)
	{
		if(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;L->r[0].key<L->r[j].key;j--)
				L->r[j+1]=L->r[j];
			L->r[j+1]=L->r[0];
		}
	}
}


void Init(sqlist *L)   //初始化顺序表
{

	int i;
	L->length=maxsize;
	for(i=1;i<=L->length;i++)
	{
       L->r[i].name=(char*)malloc(100);
	   L->r[i].key=a[i-1];
	   strcpy(L->r[i].name,b[i-1]);
	   L->r[i].next=0;           //为表插入排序作准备
	   }
}


void print(sqlist *L)   //顺序表输出函数
{
	int i;
	for(i=1;i<=L->length;i++)
	{
		printf("%d    ",L->r[i].key);
		//printf("%s",L->r[i].name);
		//printf("\n");
		if(i%10==0)
			printf("\n");
	}
}


void BInsertsort(sqlist *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)
		{
			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];
	}
}

void TInsertsort(sqlist *La)  //二路插入排序序
{

int i,j,low,high,mid,first,final;
sqlist Lb;
    first=La->length;final=1;
	Lb.r[final]=La->r[1];
//	Lb.r[first]=La->r[1];
	Lb.length=La->length;
	//printf("%d*****",Lb.r[first].key);
	for(i=2;i<=La->length;i++)
	{
		if(La->r[i].key>=La->r[1].key)
		{
		/*	low=1; high=final;
			while(low<=high)
			{
				if(La->r[i].key<Lb.r[mid].key)
					high=mid-1;
				else
					low=mid+1;
			}
			for(j=final;j>=high+1;j--)
				Lb.r[j+1]=Lb. r[j];
			Lb.r[high+1]=La->r[i];*/
			low=final;
			while(Lb.r[low].key>=La->r[i].key) --low;
			for(j=final;j>=low+1;j--)
				Lb.r[j+1]=Lb.r[j];
			    Lb.r[low+1]=La->r[i];
			final++;
		}
		else
		{
			low=first; high=La->length;
			while(low<=high)
			{
				mid=(low+high)/2;
				if(La->r[i].key<Lb.r[mid].key)
					high=mid-1;
				else
					low=mid+1;
			}
			 for(j=first;j<=high;j++)
				 Lb.r[j-1]=Lb.r[j];
			  Lb.r[high]=La->r[i];
			  first--;
		}
	}
	i=1;
	for(j=first+1;j<=Lb.length;j++,i++)
		La->r[i]=Lb.r[j];
	for(j=1;j<=first;j++,i++)
		La->r[i]=Lb.r[j];
	//printf("调试中:\n");
//print(&Lb);
//printf("%d  %d\n",first,final);
}


void shellinsert(sqlist *L,int dk)  //对线性表作一次希尔排序
{
	int i,j;
	for(i=dk+1;i<=L->length;i++)
	{
		if(L->r[i].key<L->r[i-dk].key)
		{
			L->r[0]=L->r[i];
			for(j=i-dk;j>0&&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[4]={10,5,2,1},t=4,k;
	for(k=0;k<t;k++)
		shellinsert(L,dlta[k]);
	//shellinsert(L,1);
}


int partition(sqlist *L,int low,int high)  //快速排序中对序列的划分
{
    int pivotkey;
	L->r[0]=L->r[low];
	pivotkey=L->r[low].key;
	while(low<high)
	{
		while(low<high&&L->r[high].key>=pivotkey)   	--high;
		L->r[low]=L->r[high];
		while(low<high&&L->r[low].key<=pivotkey)    	++low;
		L->r[high]=L->r[low];
	}
	L->r[low]=L->r[0];
	return low;
}

void Qsort(sqlist *L,int low,int high)   //快速排序
{
	int pivotloc;
	if(low<high)
	{
		pivotloc=partition(L,low,high);
		Qsort(L,low,pivotloc-1);
		Qsort(L,pivotloc+1,high);
	}
}

void Quicksort(sqlist *L)   //快速排序的函数接口
{
	Qsort(L,1,L->length);
}



void HeapAdjust(sqlist *H,int s,int m)  //堆调整
{
   redtype rc;
   int j;
	rc=H->r[s];
	for(j=2*s;j<=m;j=j*2)
	{
		if(j<m&&H->r[j].key<H->r[j+1].key)  ++j;
		if(rc.key>=H->r[j].key)    break;
		H->r[s]=H->r[j];
		s=j;
	}
	H->r[s]=rc;
}

void Heapsort(sqlist *H)   //堆排序
{
	int i;
	redtype t;
	for(i=H->length/2;i>0;--i)
		HeapAdjust(H,i,H->length);
	for(i=H->length;i>1;--i)
	{
		t=H->r[1];
		H->r[1]=H->r[i];
		H->r[i]=t;
	  HeapAdjust(H,1,i-1);
	}
}
 



void SInsertsort(sqlist *L)  //表插入排序
{
	int p,q,i;
	L->r[0].next=1;
	for(i=2;i<=L->length;i++)
	{
		q=L->r[0].next;
		p=0;
		while(L->r[i].key>=L->r[q].key&&L->r[q].next!=0)
		{
			p=q;
			q=L->r[i].next;
		}
		if(L->r[q].next!=0)
		{
			L->r[i].next=q;
			L->r[p].next=i;
		}
		else
			L->r[q].next=i;
	}
}

 void arrage(sqlist *L)     //静态有序表的调整
{
	int p,q,i;
	redtype t;
	 p=L->r[0].next;
	for(i=1;i<=L->length;i++)
	{
		while(p<i)
			p=L->r[p].next;
		q=L->r[p].next;
		if(p!=i)
		{
			t=L->r[p];
			L->r[p]=L->r[i];
			L->r[p]=t;
			L->r[i].next=p;
		}
		p=q;
	}
}

void linksor(sqlist &L,int d,int n)  //链式基数排序
{
	queue *f[n],*r[n];
	




void main()
{
	sqlist L;
	Init(&L);
	printf("未排序前，原始表数据为:\n");
	print(&L);
     //Insertsort(&L);
  	 //BInsertsort(&L);
      //TInsertsort(&L);
	 //shellsort(&L);
    //Quicksort(&L);
	//Heapsort(&L);
	//SInsertsort(&L);
	//arrage(&L);
	printf("排序后，所得数据为:\n");
	print(&L);
}