sort.h

实现多种排序算法比较 数据结构：用链表实现

#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#include "windows.h"
#include "time.h"

#define MAXSIZE 30000
typedef struct{
	int key;
}RedType;
typedef struct{
	RedType r[MAXSIZE+1];  //r[0]为哨兵
	int length;
}SqList;

static int exchangeCount;
static int compareCount;

/**************************************************************************************************************** 
                                                    线性表的初始化及输出
*****************************************************************************************************************/

//随机产生整数,初始化L
void InitSqList(SqList &L,int N){	
	int i;
	for(i=1;i<=N;i++){	
		L.r[i].key=rand();
	}
	L.length=N;

	exchangeCount=0;
    compareCount=0;
}

//输出序列
void PrintSqList(SqList L){
	int i;
	for(i=1;i<=L.length;i++)
	{
		printf("%-6d",L.r[i].key);
		if(i%10==0) printf("\n");
	}
}

//判断a是否小于b
int LT(int a,int b){
	if(a<b) return 1;
	else return 0;
}

/****************************************************************************************************************  
                                                     时钟函数
****************************************************************************************************************/

int GetTime() 
{
	SYSTEMTIME  time;
	GetLocalTime(&time);
	return((60*time.wMinute+time.wSecond)*1000+time.wMilliseconds);
}

/**************************************************************************************************************** 
                                                    直接插入排序
*****************************************************************************************************************/
void InsertSort(SqList &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];
			exchangeCount++;
			for(j=i-2;LT(L.r[0].key,L.r[j].key);j--)
			{
				L.r[j+1]=L.r[j];//记录后移
				exchangeCount++;
				compareCount++;
			}
			compareCount++;//对于语句for(j=i-2;LT(L.r[0].key,L.r[j].key);j--)终止时的一次，
			                 //不会执行L.compareCount++;但实际已经比较了一次；
			L.r[j+1]=L.r[0];
		}//if
		compareCount++;
	}//for
}//InsertSort

/*****************************************************************************************************************  
                                                  折半插入排序
*****************************************************************************************************************/
void BInsertSort(SqList &L){
	int i,j;
	int 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(LT(L.r[0].key,L.r[mid].key)) high=mid-1;
			else low=mid+1;
			compareCount++;
		}//while
		for(j=i-1;j>=high+1;j--)
		{
			L.r[j+1]=L.r[j];
			exchangeCount++;
		}
		L.r[high+1]=L.r[0];
	}//for
}//BInsertSort

/**************************************************************************************************************** 
                                                  起泡排序
*****************************************************************************************************************/
void BubbleSort(SqList &L){
	int i,j;
	int lastexchangeIndex;
	i=L.length;
	while(i>1){
		lastexchangeIndex=1; //假如序列本来已经有序，则i直接置1
		for(j=1;j<i;j++)
		{
			if(LT(L.r[j+1].key,L.r[j].key))
			{
				int midkey;
				midkey=L.r[j].key;
				L.r[j].key=L.r[j+1].key;
				L.r[j+1].key=midkey;

				exchangeCount++;
				lastexchangeIndex=j;
			}
			compareCount++;
		}//for
		i=lastexchangeIndex;
	}//while
}

/*****************************************************************************************************************  
                                                    选择排序
*****************************************************************************************************************/
void SelectSort(SqList &L){
	int i,j,k;
	RedType t;
	for(i=1;i<=L.length;i++)
	{
		k=i;
		for(j=i+1;j<=L.length;j++)
		{
			if(L.r[j].key<L.r[k].key) k=j;//选择L.r[i...L.length]中key最小的记录
			compareCount++;
		}
		if(k!=i)
		{
			t=L.r[k];L.r[k]=L.r[i];L.r[i]=t;
			exchangeCount++;
		}
	}//for
}//SelectSort

/**************************************************************************************************************** 
                                                      快速排序
****************************************************************************************************************/
int Partition(SqList &L,int low,int high){
	L.r[0]=L.r[low];
	int pivotkey;
	pivotkey=L.r[low].key;
	while(low<high){
		while(low<high&&L.r[high].key>=pivotkey) 
		{
			high--;
			compareCount++;
		}
		L.r[low]=L.r[high];
		exchangeCount++;
		while(low<high&&L.r[low].key<=pivotkey) 
		{
			low++;
			compareCount++;
		}
		L.r[high]=L.r[low];
		exchangeCount++;
	}
	L.r[low]=L.r[0];
	return low;
}//Partition

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);
	}
}//QSort

void QuickSort(SqList &L){
	QSort(L,1,L.length);
}//QuickSort


/****************************************************************************************************************  
                                                      堆排序
****************************************************************************************************************/
void HeapAdjust(SqList &L,int s,int m){
	RedType rc;
	rc=L.r[s];
	int j;
	for(j=2*s;j<=m;j*=2){
		if(j<m&&L.r[j].key<L.r[j+1].key)
		{
			j++;
			compareCount++;
		}
		if(rc.key>=L.r[j].key)
		{
			compareCount++;
			break;
		}
		L.r[s]=L.r[j];
		s=j;
	}
	L.r[s]=rc;
}//HeapAdjust

void HeapSort(SqList &L){
	int i;
	for(i=L.length/2;i>0;i--)
		HeapAdjust(L,i,L.length);
	for(i=L.length;i>1;i--){
		RedType t;
		t=L.r[1];
		L.r[1]=L.r[i];
		L.r[i]=t;
		exchangeCount++;
		HeapAdjust(L,1,i-1);
	}
}//HeapSort

/****************************************************************************************************************  
                                                      基数排序
****************************************************************************************************************/
#define MAX_NUM_OF_KEY  6
#define RADIX 10
#define MAX_SPACE 10000

typedef struct{
	int num; //数据值
	int Keys[MAX_NUM_OF_KEY]; //关键字
	int next;
}SLCell;

typedef struct{
	SLCell r[MAX_SPACE];
	int keynum;  //当前关键字个数
	int recnum;  //静态链表的当前长度
}SLList;
typedef int ArrType[RADIX];

void InitSLList(SLList &S,int N){
	exchangeCount=0;
    compareCount=0;

	S.keynum=MAX_NUM_OF_KEY;
	S.recnum=N;
	int m;
	for(m=0;m<S.recnum;m++) S.r[m].next=m+1;
	S.r[S.recnum].next=0;

	int i,j;
	for(i=1;i<=N;i++){
		S.r[i].num=rand();
		int t=1;
		int c=0;
		for(j=S.keynum-1;j>=0;j--)
		{  
			S.r[i].Keys[j]=(S.r[i].num%(10*t))/t; //取各位数字（即关键字）存入数组
			t*=10;
		    c++;
			if(c==S.keynum) break;
		}	
	}
}

void PrintSLList(SLList L)
{
	int i;
	int t=0;
	for(i=L.r[0].next;i>0;i=L.r[i].next)
	{
		printf("%-6d",L.r[i].num);
		t++;
		if(t%10==0) printf("\n");
	}
}

void Distribute(SLList &L,int i,ArrType &f,ArrType &e){
	int j;
	for(j=0;j<RADIX;j++) f[j]=0;
	int p;
	for(p=L.r[0].next;p!=0;p=L.r[p].next){
		j=L.r[p].Keys[L.keynum-i-1];
		if(!f[j]) f[j]=p;
		else L.r[e[j]].next=p;
		e[j]=p;
	}
}//Distribute

void Collect(SLList &L,int i,ArrType f,ArrType e){
	int j,t;
	for(j=0; !f[j]; j++);//找第一个非空子表
	L.r[0].next=f[j];
	t=e[j];
	while(j<RADIX){
		for(j++; j<RADIX&&!f[j]; j++);//找下一个非空子表
		if(j==RADIX)break;
		if(f[j]) {L.r[t].next=f[j];t=e[j];}
	}
	L.r[t].next=0;
}//Collect

void RadixSort(SLList &L){
	int i;
	ArrType f,e;
	for(i=0;i<L.keynum;i++){
		Distribute(L,i,f,e);
		Collect(L,i,f,e);
	}
}//RadixSort

/****************************************************************************************************************  
                                                    end...
****************************************************************************************************************/