sort.bak

测试各种排序算法,使用VC.NET进行开发

//排序算法
//by lordor 2005.08.20
#include "stdafx.h"

//数据结构
const int maxsize=100;	//排序表容量，假设为100
typedef int datatype;	//假设关键字为int
typedef struct { 
	datatype key;		//关键字域
//	othertype other;		//其它域
} rectype;				//记录类型
typedef rectype list[maxsize+1];
//排序表类型，0号单元不用（或作它用，如“监视哨”）


//直接插入排序
void InsertSort(list R,int n) { //有监视哨
	int i,j;
	　for(i=2;i<=n;i++) { //进行n-1次插入
		 if(R[i].key>=R[i-1].key) continue;
		 R[0]=R[i];        //R[0]是监视哨
		 j=i-1;
		 do {              //顺序比较和移动
			 R[j+1]=R[j];j--;
		 } while(R[0].key<R[j].key); 
		 R[j+1]=R[0];      //插入R[i]
	 }
}


//希尔排序
void ShellInsert(list R,int n,int h){
	//一趟插入排序，h为本趟增量
	int i,j,k;
	for(i=1;i<=h;i++)		//i为组号
		for(j=i+h;j<=n;j+=h) {//每组从第2个记录开始插入
			if(R[j].key>=R[j-h].key) continue;
			R[0]=R[j];	//R[0]保存待插记录，但不是监视哨
			k=j-h;		//待插记录的前一个记录
			do{		//查找插入位置
				R[k+h]=R[k];k=k-h;//后移记录，继续向前搜索
			} while(k>0 && R[0].key<R[k].key);
			R[k+h]=R[0];	//插入R[j]
		}
}

//调用希尔
void ShellSort(list R,int n,int d[],int t) {
	//d[]为增量序列，t为增量序列长度
	int i;
	for(i=0;i<t;i++)		    //各趟插入排序
		ShellInsert(R,n,d[i]);
}


//冒泡排序
void BubbleSort(list R,int n) {//上升法冒泡排序
	int i,j,flag;
	for(i=1;i<=n-1;i++) {		//做n-1趟扫描
		flag=0;				//置未交换标志
		for(j=n;j>=i+1;j++)		//从下向上扫描
			if(R[j].key<R[j-1].key) {//交换记录
				flag=1;
				R[0]=R[j];R[j]=R[j-1];R[j-1]=R[0];
				//交换，R[0]作辅助量 
			}
			if(!flag) break;	  //本趟未交换过，排序结束
	}
}



//快递排序
int Partition(list R,int p,int q) {	
	//对无序区R[p]到R[q]划分，返回划分后基准的位置
	int i,j;
	i=p;  j=q;   R[0]=R[i];
	//R[0]作辅助量，存基准(无序区第一个记录)
	while(i<j) {
		while(R[j].key>=R[0].key && i<j) j--;
		//从右向左扫描
		if(i<j) {R[i]=R[j];i++;}	//交换R[i]和R[j]
		while(R[i].key<=R[0].key && i<j) i++;
		//从左向右扫描
		if(i<j) {R[j]=R[i];j--;}	//交换R[i]和R[j]
	}
	R[i]=R[0];			//将基准移到最后位置
	return i;
}

//快速排序
void QuickSort(list R,int s,int t) {
	//对R[s]到R[t]快速排序
	int i;
	if(s>=t) return;	//只有一个记录或无记录无需排序
	i=Partition(R,s,t);	//对R[s]到R[t]做划分
	QuickSort(R,s,i-1);	//递归处理左区间
	QuickSort(R,i+1,t);	//递归处理右区间
}



//直接选择排序
void SelectSort(list R,int n) {
	int i,j,k;
	for(i=1;i<=n-1;i++) {	//n-1趟排序
		k=i;
		for(j=i+1;j<=n;j++)	//无序区中找最小R[k]
			if(R[j].key<R[k].key) k=j;
		if(k!=i) {R[0]=R[i];R[i]=R[k];R[k]=R[0];}
		　　　　　　　　　　//交换R[i]和R[k]，R[0]作辅助
	}
}


//堆排序

void Sift(list R,int p,int q) {
	//筛选，范围R[p]～R[q]，非递归
	int i,j;
	R[0]=R[p];		//R[0]辅助量，保存原根结点
	i=p;			//i指向待调整点
	j=2*i;			//j指向R[i]的左孩子
	while(j<=q) {    //无左孩子，必叶子，结束
		if(j<q && R[j].key<R[j+1].key) j++;
		　　　　　　　　　　　　//j指向R[i]的右孩子
		if(R[0].key>R[j].key) break;	
		　　　　　　　　　　　　//根＞孩子，已堆，调整结束
		R[i]=R[j];	//将R[j]换到双亲位置上
		i=j;			//修改当前被调整结点
		j=2*i;		//j指向R[i]的左孩子
	}
	R[i]=R[0];		//原根结点放入正确位置
}

void Sift2(list R,int p,int q) {
	　//筛选，范围R[p]～R[q]，递归
	int i,j;
	if(p>=q) return;	//只有一个元素或无元素
	i=p;			//i指向待调整点
	j=2*i; 			//j指向R[i]的左孩子
	if(j<q && R[j].key<R[j+1].key) j++;
	　　　　　　　　　　　　//j指向R[i]的右孩子
	if(R[i].key>R[j].key) return;
	　　　　　　　　　　　　//待调点已最大，不调
	R[0]=R[j];R[j]=R[i];R[i]=R[0];
	　　　　　　　　　　　　//交换R[j]和R[i]，R[0]作辅助
	Sift2(R,j,q);	//递归
}



void HeapSort(list R,int n) {
	//对R[1]到R[n]进行堆排序
	int i;
	for(i=n/2;i>=1;i--) Sift(R,i,n);	//建初始堆
	for(i=n;i>=2;i--) {//进行n-1趟堆排序
		R[0]=R[1];R[1]=R[i];R[i]=R[0];
		　　　　　　　　　　//堆顶和当前堆底交换，R[0]作辅助量
		Sift(R,1,i-1);　//R[1]到R[i-1]重建成新堆
	}
}




//归并排序
void Merge(list R,list R1,int low,int mid,int high)
{
	//合并R[low]~R[mid]、R[mid+1]~R[high]，结果在R1中
	int i,j,k;
	i=low;j=mid+1;k=low; 
	while(i<=mid && j<=high)
		if(R[i].key<=R[j].key) R1[k++]=R[i++]; //小者
		else R1[k++]=R[j++];
		while(i<=mid) R1[k++]=R[i++]; //复制左子表剩余
		while(j<=high) R1[k++]=R[j++]; //复制右子表剩余
}



void MergePass(list R,list R1,int n,int len) {
	//对R做一趟归并，结果在R1中
	int i,j;
	i=1;			//i指向第一对子表的起始点
	while(i+2*len-1<=n) {	//归并长度为len的两个子表
		Merge(R,R1,i,i+len-1,i+2*len-1);
		i=i+2*len;	//i指向下一对子表起始点
	}
	if(i+len-1<n)	//剩两子表，一个长度小于len
		Merge(R,R1,i,i+len-1,n); 
	else			//子表个数为奇数,剩一段
		for(j=i;j<=n;j++)//将最后一个子表复制到R1中
			R1[j]=R[j];
}

void MergeSort(list R,list R1,int n) {
	　//对R二路归并排序，结果在R中(非递归)
	int len;
	len=1;
	while(len<n) {
		MergePass(R,R1,n,len);len=len*2;
		//一趟归并，结果在R1中
		MergePass(R1,R,n,len);len=len*2;
		//再次归并，结果在R中
	}
}