基于比较的内部排序总结

转自：爪哇人

 

#include<iostream.h>
#include<time.h>
#include<stdlib.h>

#define MIN_ELEMENT_NUM 100000
#define MAX_ELEMENT_NUM 1500000
#define INCREMENT_NUM 100000

//产生随机数
double random(double start, double end)  
{  
	return start+(end-start)*rand()/(RAND_MAX + 1.0);  
} 
//产生iElementNum个随机数的待排序列数组pArray[]
void fill_array(int *pArr,int num)
{
	for(int i=0; i<num; i++)
        pArr[i] = int(random(0,100000));
}

/********************
 *   直接插入排序   *
 ********************/
void straight_insertion_sort(int *pArr,int size){
	int post_key;  //记录当前要插入的key  
	for(int i=1;i<size;i++){  	//从第二个数据开始  
		post_key=pArr[i];  
		int j;  	
		for(j=i-1;j>=0;j--){  //将比post_key要大的前面所有的key依次后移一位  
			if(post_key<pArr[j])  
				pArr[j+1]=pArr[j];  
			else  
				break;  
		}  
		pArr[j+1]=post_key;  //将post_key插入到合适位置  
	} 
}

/********************
 *   折半插入排序   *
 ********************/
void binary_insertion_sort(int *pArr,int size){
	int post_key;  
	for(int i=1;i<size;i++){  
		post_key=pArr[i];  
		int low=0,high=i-1;  //折半查找  
		while(low<=high){  
			int middle=(low+high)/2;  
			if(post_key<pArr[middle])  
				high=middle-1;  
			else low=middle+1;  
		}  
		for(int j=i-1;j>=high+1;j--)  //移动位置  
			pArr[j+1]=pArr[j];  
		pArr[high+1]=post_key;  
	}  

}
/*****************
 *   希尔排序    *
 *****************/
void shell_sort(int *pArr,int size){
	int increment=size; //增量
	do{
		increment=increment/3+1; //增量逐步减少至1
		int post_key;  
		for(int i=increment;i<size;i++){  
			if(pArr[i]<pArr[i-increment]){  
				post_key=pArr[i];  
				for(int j=i-increment;j>=0&&post_key<pArr[j];j=j-increment)
					pArr[j+increment]=pArr[j];  
				pArr[j+increment]=post_key;  
			}
		} 	
	}while(increment>1);
}  
/*****************
 *   起泡排序    *
 *****************/
void bubble_sort(int *pArr,int size){
	for(int i=size-1;i>=0;i--)  
		for(int j=0;j<i;j++)
			if(pArr[j]>pArr[j+1]){  
				int temp=pArr[j];  
				pArr[j]=pArr[j+1];  
				pArr[j+1]=temp;  
			}  
}

/*****************
 *   快速排序    *
 *****************/
void quick_sort(int *pArr, int size){
	int * beginIdxs=(int *)malloc(size * sizeof(int)); //记录待调整子序列的首地址
	int * endIdxs=(int *)malloc(size * sizeof(int));//记录待调整子序列的尾地址
	beginIdxs[0]=0;
	endIdxs[0]=size-1;
	int curIdx=0;
	while(curIdx>-1){
		int low=beginIdxs[curIdx];
		int high=endIdxs[curIdx];
		int pivotkey=pArr[low]; //将第一个元素作为枢轴  
		while(low<high){
			while(low<high && pivotkey<=pArr[high]) --high;
			pArr[low]=pArr[high];
			while(low<high && pivotkey>=pArr[low]) ++low;
			pArr[high]=pArr[low];
		}
		pArr[low]=pivotkey;
		int pivotidx=low;
		int begin=beginIdxs[curIdx];
		int end=endIdxs[curIdx];
		curIdx--;
		if(begin<pivotidx-1){
			beginIdxs[++curIdx]=begin;
			endIdxs[curIdx]=pivotidx-1;
		}
		if(end>pivotidx+1){
			beginIdxs[++curIdx]=pivotidx+1;
			endIdxs[curIdx]=end;
		}
	}
}
/********************
 *   简单选择排序   *
 ********************/
void simple_selection_sort(int *pArr, int size){
	for(int i=0;i<size;i++){       
		int min_key=pArr[i]; //存储每一趟排序的最小值  
		int min_key_pos=i;   //存储最小值的位置  
		for(int j=i+1;j<size;j++){  
			if(min_key>pArr[j]){ //定位最小值  
				min_key=pArr[j];  
				min_key_pos=j;  
			}  
		}     
		pArr[min_key_pos]=pArr[i]; //将选择的最小值交换位置  
		pArr[i]=min_key;      
	}  
}
/************************************************
 *    树形选择排序(锦标赛排序Tournament Sort)   *
 ************************************************/
#define MAX_INT 32767;  

typedef struct sort_node{  
	int key; //待排关键字  
	int pos; //此关键字在待排序列中的位置  
}SortNode; 

void tree_selection_sort(int *pArr,int size){  
	
	int level=1;  
	SortNode **level_point;  
	//记录每一层的关键字容量的连续空间  
	int *level_count;  
	//记录已经排序号的关键字序列  
	int *sorted_keys;  
	
	//开辟存储排序序列的容量  
	sorted_keys=(int *)malloc(size*sizeof(int));  

	//根据待排序列的数量确定排序树的层次  
	int a_size=size;  
	bool isPower=true;  
	if(a_size>1){  
		while(a_size!=1){  
			if(a_size%2==1)  
				isPower=false;  
			level++;  
			a_size/=2;  
		}  
	}  
	if(isPower==false) level++;  
   
	//构造排序树的内存结构，为每一层开辟可以容纳一定数量关键字的内存空间  
	level_point=(SortNode **)malloc(level*sizeof(SortNode *));  
	level_count=(int *)malloc(level*sizeof(int));  
	int level_size=size;  
	for(int l=0;l<level;l++){  
		level_count[l]=level_size;  
		level_point[l]=(SortNode *)malloc(level_size*sizeof(SortNode));  
		level_size=level_size/2+level_size%2;  
	}  

	//为第0层赋值待排序列，并建立排序树，找到第一次最小的关键字  
	for(int i=0;i<size;i++){  
		level_point[0][i].key=pArr[i];  
		level_point[0][i].pos=i;  
	}  
	int cur_level=1;  
	while(cur_level<level){  
		for(int j=0;j<level_count[cur_level];j++){  
			int left_child=level_point[cur_level-1][j*2].key;  
			//没有右孩子  
			if((j*2+1)>=level_count[cur_level-1]){  
				level_point[cur_level][j].key=left_child;  
				level_point[cur_level][j].pos=level_point[cur_level-1][j*2].pos;  
			}else{  
				int right_child=level_point[cur_level-1][j*2+1].key;  
				level_point[cur_level][j].key=left_child<=right_child ? left_child : right_child;  
				level_point[cur_level][j].pos=left_child<=right_child ? level_point[cur_level-1][j*2].pos : level_point[cur_level-1][j*2+1].pos;  
			}  
		}  
		cur_level++;  
	}  
	//第一次树形排序的最小值和最小位置  
	int cur_min_key=level_point[level-1][0].key;  
	int cur_min_pos=level_point[level-1][0].pos;  
	sorted_keys[0]=cur_min_key;  
	//输出剩下size-1个最小的数  
	for(int count=1;count<=size-1;count++){  
		level_point[0][cur_min_pos].key=MAX_INT;      
		//找到需要重新比较的两个位置  
		int a_pos=cur_min_pos;  
		int b_pos=a_pos%2==0 ? a_pos+1 : a_pos-1;  
		for(int m=1;m<level;m++){  
			if(b_pos>=level_count[m-1]){  
				level_point[m][a_pos/2].key=level_point[m-1][a_pos].key;  
				level_point[m][a_pos/2].pos=level_point[m-1][a_pos].pos;  
			}else{  
				level_point[m][a_pos/2].key=level_point[m-1][a_pos].key<=level_point[m-1][b_pos].key ? level_point[m-1][a_pos].key : level_point[m-1][b_pos].key;  
				level_point[m][a_pos/2].pos=level_point[m-1][a_pos].key<=level_point[m-1][b_pos].key ? level_point[m-1][a_pos].pos : level_point[m-1][b_pos].pos;  
			}  
			a_pos=a_pos/2;  
			b_pos=a_pos%2==0 ? a_pos+1 : a_pos-1;  
		}  
		//记录每一次树形排序的最小值和对应的位置  
		cur_min_key=level_point[level-1][0].key;  
		cur_min_pos=level_point[level-1][0].pos;  
		sorted_keys[count]=cur_min_key;  
	}   	
	free(level_count);  
	free(sorted_keys);  
	for(int k=0;k<level;k++)  
		free(level_point[k]);   
}

/***************
 *   堆排序    *
 ***************/
//交换
void swap(int *pArr,int pos_a,int pos_b){  
	int temp=pArr[pos_a];  
	pArr[pos_a]=pArr[pos_b];  
	pArr[pos_b]=temp;  
}  
//创建堆  
void create(int *pArr,int size){  
	for(int i=(size-1)/2;i>=0;i--){        
		int lchild=i*2+1;  
		int rchild=i*2+2;  
		while(lchild<size){  
			int next_pos=-1;  
			if(rchild>=size&&pArr[i]>pArr[lchild]){  
				swap(pArr,i,lchild);  
				next_pos=lchild;  
			}  
			if(rchild<size){  
				int min_temp=pArr[lchild]<=pArr[rchild] ? pArr[lchild] : pArr[rchild];  
				int min_pos=pArr[lchild]<=pArr[rchild] ? lchild : rchild;  
				if(pArr[i]>pArr[min_pos]){  
					swap(pArr,i,min_pos);  
					next_pos=min_pos;  
				}  
			}  
			if(next_pos==-1) break;  
			lchild=next_pos*2+1;  
			rchild=next_pos*2+2;  
		}  
	}  
} 
//调整堆  
void adjust(int *pArr,int var_size){  

	int pos=0;  
	while((pos*2+1)<var_size){  
		int next_pos=-1;  
		if((pos*2+2)>=var_size&&pArr[pos]>pArr[pos*2+1]){  
			swap(pArr,pos,pos*2+1);  
			next_pos=pos*2+1;  
		}  
		if((pos*2+2)<var_size){  
			int min_keys=pArr[pos*2+1]<=pArr[pos*2+2] ? pArr[pos*2+1] : pArr[pos*2+2];  
			int min_pos=pArr[pos*2+1]<=pArr[pos*2+2] ? (pos*2+1) : (pos*2+2);  
			if(pArr[pos]>min_keys){  
				swap(pArr,pos,min_pos);  
				next_pos=min_pos;  
			}  
		}  
		if(next_pos==-1) break;  
		pos=next_pos;  
	}         
}  
void heap_sort(int *pArr,int size){
	create(pArr,size);
	int var_size=size;  
	while(var_size>0){  
		pArr[0]=pArr[var_size-1];  
		--var_size;  
		adjust(pArr,var_size);  
	}  
}


/*************
 * 归并排序  *
 *************/
//合并
void merge(int *pArr, int *merged, int si, int mi, int ti){  

	//把已近排序号的si-mi，mi-ti两个序列赋值给raw  
	for(int t=si;t<=ti;t++)  
		pArr[t]=merged[t];  
	//归并  
	int i=si,j=mi+1,k=si;  
	for(;i<=mi&&j<=ti;){  
		if(pArr[i]<=pArr[j]) merged[k++]=pArr[i++];  
		else merged[k++]=pArr[j++];  
	}  
	if(i<=mi)  
		for(int x=i;x<=mi;)  
			merged[k++]=pArr[x++];  
	if(j<=ti)  
		for(int y=j;y<=ti;)  
			merged[k++]=pArr[y++];  
}  
//划分  
void partition(int *pArr, int *merged, int s, int t){  

	if(s==t) merged[s]=pArr[s];  
	else{  
		int m=(s+t)/2;  
		partition(pArr, merged, s, m);  
		partition(pArr, merged, m+1,t);  
		merge(pArr, merged, s,m,t);  
	}  
}  

void merge_sort(int *pArr,int size){  
	int * merged=(int *)malloc(size*sizeof(int));  
	partition(pArr,merged,0,size-1);  
	free(merged);  
}  



void main()
{
	srand(unsigned(time(0))); 

	//每次产生一组数量递增的待排序列
	for(int elementNum=MIN_ELEMENT_NUM;elementNum<=MAX_ELEMENT_NUM;elementNum+=INCREMENT_NUM){
		int ctRun=0;
		int avgNum;
		for(avgNum=0;avgNum<1;avgNum++){
			int *pArray = new int[elementNum]; //待排序列数组
			fill_array(pArray,elementNum);
			clock_t ctBegin = clock();
			//straight_insertion_sort(pArray,elementNum); //直接插入排序
			//binary_insertion_sort(pArray,elementNum); //折半插入排序
			shell_sort(pArray,elementNum); //希尔排序
			//bubble_sort(pArray,elementNum);//起泡排序
			//quick_sort(pArray,elementNum); //快速排序
			//simple_selection_sort(pArray,elementNum);//简单选择排序
			//tree_selection_sort(pArray,elementNum); //树形选择排序
			//heap_sort(pArray,elementNum);//堆排序
			//merge_sort(pArray,elementNum);    //归并排序
			clock_t ctEnd = clock();
			ctRun+=(ctEnd-ctBegin);
			delete[] pArray;
		}
		ctRun/=avgNum;
		cout<<"size="<<elementNum<<"   avg time="<<ctRun<<"ms"<<endl;
	}
}