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

//數(shù)據(jù)結(jié)構(gòu)
const int maxsize=100;	//排序表容量，假設(shè)為100
typedef int datatype;	//假設(shè)關(guān)鍵字為int
typedef struct { 
	datatype key;		//關(guān)鍵字域
//	othertype other;		//其它域
} rectype;				//記錄類型
typedef rectype list[maxsize+1];
//排序表類型，0號單元不用（或作它用，如“監(jiān)視哨”）


//直接插入排序
void InsertSort(list R,int n) { //有監(jiān)視哨
	int i,j;
	　for(i=2;i<=n;i++) { //進(jìn)行n-1次插入
		 if(R[i].key>=R[i-1].key) continue;
		 R[0]=R[i];        //R[0]是監(jiān)視哨
		 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個(gè)記錄開始插入
			if(R[j].key>=R[j-h].key) continue;
			R[0]=R[j];	//R[0]保存待插記錄，但不是監(jiān)視哨
			k=j-h;		//待插記錄的前一個(gè)記錄
			do{		//查找插入位置
				R[k+h]=R[k];k=k-h;//后移記錄，繼續(xù)向前搜索
			} while(k>0 && R[0].key<R[k].key);
			R[k+h]=R[0];	//插入R[j]
		}
}

//調(diào)用希爾
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;				//置未交換標(biāo)志
		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;	  //本趟未交換過，排序結(jié)束
	}
}



//快遞排序
int Partition(list R,int p,int q) {	
	//對無序區(qū)R[p]到R[q]劃分，返回劃分后基準(zhǔn)的位置
	int i,j;
	i=p;  j=q;   R[0]=R[i];
	//R[0]作輔助量，存基準(zhǔn)(無序區(qū)第一個(gè)記錄)
	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];			//將基準(zhǔn)移到最后位置
	return i;
}

//快速排序
void QuickSort(list R,int s,int t) {
	//對R[s]到R[t]快速排序
	int i;
	if(s>=t) return;	//只有一個(gè)記錄或無記錄無需排序
	i=Partition(R,s,t);	//對R[s]到R[t]做劃分
	QuickSort(R,s,i-1);	//遞歸處理左區(qū)間
	QuickSort(R,i+1,t);	//遞歸處理右區(qū)間
}



//直接選擇排序
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++)	//無序區(qū)中找最小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]輔助量，保存原根結(jié)點(diǎn)
	i=p;			//i指向待調(diào)整點(diǎn)
	j=2*i;			//j指向R[i]的左孩子
	while(j<=q) {    //無左孩子，必葉子，結(jié)束
		if(j<q && R[j].key<R[j+1].key) j++;
		　　　　　　　　　　　　//j指向R[i]的右孩子
		if(R[0].key>R[j].key) break;	
		　　　　　　　　　　　　//根＞孩子，已堆，調(diào)整結(jié)束
		R[i]=R[j];	//將R[j]換到雙親位置上
		i=j;			//修改當(dāng)前被調(diào)整結(jié)點(diǎn)
		j=2*i;		//j指向R[i]的左孩子
	}
	R[i]=R[0];		//原根結(jié)點(diǎn)放入正確位置
}

void Sift2(list R,int p,int q) {
	　//篩選，范圍R[p]～R[q]，遞歸
	int i,j;
	if(p>=q) return;	//只有一個(gè)元素或無元素
	i=p;			//i指向待調(diào)整點(diǎn)
	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;
	　　　　　　　　　　　　//待調(diào)點(diǎn)已最大，不調(diào)
	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]進(jìn)行堆排序
	int i;
	for(i=n/2;i>=1;i--) Sift(R,i,n);	//建初始堆
	for(i=n;i>=2;i--) {//進(jìn)行n-1趟堆排序
		R[0]=R[1];R[1]=R[i];R[i]=R[0];
		　　　　　　　　　　//堆頂和當(dāng)前堆底交換，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]，結(jié)果在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++]; //復(fù)制左子表剩余
		while(j<=high) R1[k++]=R[j++]; //復(fù)制右子表剩余
}



void MergePass(list R,list R1,int n,int len) {
	//對R做一趟歸并，結(jié)果在R1中
	int i,j;
	i=1;			//i指向第一對子表的起始點(diǎn)
	while(i+2*len-1<=n) {	//歸并長度為len的兩個(gè)子表
		Merge(R,R1,i,i+len-1,i+2*len-1);
		i=i+2*len;	//i指向下一對子表起始點(diǎn)
	}
	if(i+len-1<n)	//剩兩子表，一個(gè)長度小于len
		Merge(R,R1,i,i+len-1,n); 
	else			//子表個(gè)數(shù)為奇數(shù),剩一段
		for(j=i;j<=n;j++)//將最后一個(gè)子表復(fù)制到R1中
			R1[j]=R[j];
}

void MergeSort(list R,list R1,int n) {
	　//對R二路歸并排序，結(jié)果在R中(非遞歸)
	int len;
	len=1;
	while(len<n) {
		MergePass(R,R1,n,len);len=len*2;
		//一趟歸并，結(jié)果在R1中
		MergePass(R1,R,n,len);len=len*2;
		//再次歸并，結(jié)果在R中
	}
}