【排序结构3】 选择排序

(1) 简单选择排序 O(N^2)

一趟简单选择排序的操作为：通过n-i 次关键字间的比较，从n-i+1 个记录中选择出关键字最小的记录，并和第 i (i<=i<=n)个记录交换之。

#include<iostream.h>
/*************************************** 
 * 简单选择排序 Simple Selection Sort  *  
 ***************************************/ 
class SimpleSelectSort{
public:
	//递增排序
	static void inc_sort(int keys[],int size);
};
void SimpleSelectSort :: inc_sort(int keys[], int size){
	for(int i=0;i<size;i++){		
		int min_key=keys[i]; //存储每一趟排序的最小值
		int min_key_pos=i;   //存储最小值的位置
		for(int j=i+1;j<size;j++){
			if(min_key>keys[j]){ //定位最小值
				min_key=keys[j];
				min_key_pos=j;
			}
		}	
		keys[min_key_pos]=keys[i]; //将选择的最小值交换位置
		keys[i]=min_key;	
	}
	for(int k=0;k<size;k++)
		cout<<keys[k]<<" ";
	cout<<endl;
}
//Test SimpleSelectSort
void main(){
	int raw[]={49,38,65,97,76,13,27,49}; 
	int size=sizeof(raw)/sizeof(int);   
	SimpleSelectSort::inc_sort(raw,size);    
}

 简单选择排序的时间复杂度为O(N^2)，空间复杂度为O(1)，排序方法是稳定的 。这种排序方法在n个关键字中选出最小值，至少进行n-1次比较，然而，继续在剩余的n-1个关键字中选择次小值就并非一定要进行n-2次比较了。下面的树形选择排序后一轮比较可以利用前一轮的比较结果，从而大大减少比较的次数。

 

(2) 树形选择排序 O(N * logN)

 

树形选择排序(Tree Selection Sort)，又称竞标赛排序(Tournament Sort)，是一种按照竞标赛思想进行的选择排序方法。首先对n个记录的关键字两两比较，然后在其中[n/2]个较小者之间在进行两两比较，如此重复，直至选出最小关键字的记录为止。这个过程可用一颗有n个叶子结点的完全二叉树表示。 下图展示了树形选择排序的过程：

 

(a)图选择出最小值13需要7次比较，但是(b)图选择第二小的27就只需要3次了。应为(a)图中的最小值13已经找到，只需要在(b)图中将13的位置赋值为无穷大，这样，就只需要再次比较树的一部分就可以找到第二小的值。

#include<iostream.h>
#include<malloc.h>
#define MAX_INT 32767;

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

int level=1;
SortNode **level_point;
//记录每一层的关键字容量的连续空间
int *level_count;
//记录已经排序号的关键字序列
int *sorted_keys;

//释放多维指针
void freeAll(SortNode ** deleted, int size){
	for(int i=0;i<size;i++)
		free(deleted[i]);
}
//递增排序
void inc_sort(int keys[],int size){

	//开辟存储排序序列的容量
	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=keys[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++;
	}

	//打印第一次的树形选择排序：
	cout<<"第1次树形选择排序 (关键字 - 关键字在待排表中的位置)："<<endl;
	for(int u=level-1;u>=0;u--){
		for(int i=0;i<level_count[u];i++)
			cout<<"("<<level_point[u][i].key<<"-"<<level_point[u][i].pos<<")  ";
		cout<<endl;
	}

	//第一次树形排序的最小值和最小位置
	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;

		//打印第count次的树形选择排序：
		cout<<"第"<<(count+1)<<"次树形选择排序 (关键字 - 关键字在待排表中的位置)："<<endl;
		for(int u=level-1;u>=0;u--){
			for(int i=0;i<level_count[u];i++)
				cout<<"("<<level_point[u][i].key<<"-"<<level_point[u][i].pos<<")  ";
			cout<<endl;
		}
	}
	
	//打印排序好的序列
	cout<<endl<<endl<<"排序序列：";
	for(int k=0;k<size;k++)
		cout<<sorted_keys[k]<<" ";
	cout<<endl;

	free(level_count);
	free(sorted_keys);
	freeAll(level_point,level);
}
//Test
void main(){
	int raw[]={49,38,65,97,76,13,27,49};   
	int size=sizeof(raw)/sizeof(int);     
	inc_sort(raw,size);   

}

 

树形选择排序需要建立一棵含n个叶子结点的完全二叉树，其深度为[logN]+1。因此，除第一次排序需要比较n次以外，其余每一次树形选择排序都只需要比较logN次。因此树形选择排序的时间复杂度为O(N*logN) 。但是这种排序方法大量额外的空间，一棵n个叶子结点的满二叉树有2n-1个结点。则对N个关键字的树形选择排序需要近2N左右的结点。空间复杂度为O(2N) 。该方法也是稳定的排序 。

 

树形选择排序仍然有很多缺点，比如空间代价高，需要和无穷大关键字做比较等。为了弥补，J.willioms在1964年提出了下面的另一种选择排序——堆排序。

(3) 堆排序

堆的定义如如下：n个元素的序列{K0 ... K(n-1)}，当且仅当满足下关系时，称之为堆。(注: 序列从下标0作为第一个元素开始)

                  ki <= k(2i+1) && ki <= k(2i+2)    —— 小顶堆

                  ki >= k(2i+1) && ki >= k(2i+2)    —— 大顶堆

 

若将此序列对应的一维数组(序列的内存结构)看成是一个完全二叉树，即Ki 的左孩子是K(2i+1)，右孩子是K(2i+2)。则堆的含义就是，完全二叉树中所有非终结点的值均不大于(不小于)其左、右孩子结点的值。因此，堆顶元素K0就是整个序列的最小值了。

 

堆排序的算法流程：

首先，将待排序列整理成堆。即从序列的第[n/2]-1个元素(完全二叉树最后一个非终结点)开始，到第0个结点为止调整堆。具体过程见下图：

然后，输出堆顶元素K0后，用当前堆中最后一个元素K(n-1)代替堆顶。并将待排序列减少一个(最后一个元素已经移到了第0号位置)，接着调整堆，即将移动后的堆顶元素向下调整(保证小顶堆)。具体过程如下图：

 

最后，依次循环下去，直到输出序列的全部元素为止。

#include<iostream.h>
/*********************
 * 堆排序 Heap Sort  *   
 *********************/   
class HeapSort{
public:
	//递增排序
	static void inc_sort(int keys[], int size);
private:
	//创建堆
	static void create(int keys[],int size);
	//调整堆
	static void adjust(int keys[],int var_size);
	//交换
	static void swap(int keys[],int pos_a,int pos_b);
};
//创建堆
void HeapSort :: create(int keys[],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&&keys[i]>keys[lchild]){
				HeapSort ::swap(keys,i,lchild);
				next_pos=lchild;
			}
			if(rchild<size){
				int min_temp=keys[lchild]<=keys[rchild] ? keys[lchild] : keys[rchild];
				int min_pos=keys[lchild]<=keys[rchild] ? lchild : rchild;
				if(keys[i]>keys[min_pos]){
					swap(keys,i,min_pos);
					next_pos=min_pos;
				}
			}
			if(next_pos==-1) break;
			lchild=next_pos*2+1;
			rchild=next_pos*2+2;
		}
	}
}
//调整堆
void HeapSort :: adjust(int keys[],int var_size){

	int pos=0;
	while((pos*2+1)<var_size){
		int next_pos=-1;
		if((pos*2+2)>=var_size&&keys[pos]>keys[pos*2+1]){
			swap(keys,pos,pos*2+1);
			next_pos=pos*2+1;
		}
		if((pos*2+2)<var_size){
			int min_keys=keys[pos*2+1]<=keys[pos*2+2] ? keys[pos*2+1] : keys[pos*2+2];
			int min_pos=keys[pos*2+1]<=keys[pos*2+2] ? (pos*2+1) : (pos*2+2);
			if(keys[pos]>min_keys){
				swap(keys,pos,min_pos);
				next_pos=min_pos;
			}
		}
		if(next_pos==-1) break;
		pos=next_pos;
	}		
}
//递增排序
void HeapSort :: inc_sort(int keys[], int size){
	HeapSort::create(keys,size);
	int var_size=size;
	while(var_size>0){
		cout<<keys[0]<<" "; //Êä³öÿһÂÖ¶ÑÅÅÐòµÄ×îСֵ
		keys[0]=keys[var_size-1];
		--var_size;
		adjust(keys,var_size);
	}
}
//keys[pos_a]  <-> keys[pos_b]
void HeapSort :: swap(int keys[],int pos_a,int pos_b){
	int temp=keys[pos_a];
	keys[pos_a]=keys[pos_b];
	keys[pos_b]=temp;
}
//Test HeapSort
void main(){
	int raw[]={49,38,65,97,76,13,27,49};     
	int size=sizeof(raw)/sizeof(int);       
	HeapSort::inc_sort(raw,size);     
}

 

堆排序方法对记录较少的文件效果一般，但对于记录较多的文件还是很有效的。其运行时间主要耗费在创建堆和反复调整堆上。堆排序即使在最坏情况下，其时间复杂度也为O(N*logN) 。这一点比快速排序 要好。另外，堆排序所需要的空间复杂度为O(1) 。但却是不稳定排序 。