(1) 簡(jiǎn)單選擇排序 O(N^2)

一趟簡(jiǎn)單選擇排序的操作為：通過n-i 次關(guān)鍵字間的比較，從n-i+1 個(gè)記錄中選擇出關(guān)鍵字最小的記錄，并和第 i (i<=i<=n)個(gè)記錄交換之。

    #include<iostream.h>
/*************************************** 
 * 簡(jiǎn)單選擇排序 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]; //存儲(chǔ)每一趟排序的最小值
		int min_key_pos=i;   //存儲(chǔ)最小值的位置
		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);    
}
  

?簡(jiǎn)單選擇排序的 時(shí)間復(fù)雜度為O(N^2)，空間復(fù)雜度為O(1)，排序方法是穩(wěn)定的 。這種排序方法在n個(gè)關(guān)鍵字中選出最小值，至少進(jìn)行n-1次比較，然而，繼續(xù)在剩余的n-1個(gè)關(guān)鍵字中選擇次小值就并非一定要進(jìn)行n-2次比較了。下面的樹形選擇排序后一輪比較可以利用前一輪的比較結(jié)果，從而大大減少比較的次數(shù)。

?

(2) 樹形選擇排序 O(N * logN)

?

樹形選擇排序(Tree Selection Sort)，又稱競(jìng)標(biāo)賽排序(Tournament Sort)，是一種按照競(jìng)標(biāo)賽思想進(jìn)行的選擇排序方法。首先對(duì)n個(gè)記錄的關(guān)鍵字兩兩比較，然后在其中[n/2]個(gè)較小者之間在進(jìn)行兩兩比較，如此重復(fù)，直至選出最小關(guān)鍵字的記錄為止。這個(gè)過程可用一顆有n個(gè)葉子結(jié)點(diǎn)的完全二叉樹表示。 下圖展示了樹形選擇排序的過程：

?

(a)圖選擇出最小值13需要7次比較，但是(b)圖選擇第二小的27就只需要3次了。應(yīng)為(a)圖中的最小值13已經(jīng)找到，只需要在(b)圖中將13的位置賦值為無(wú)窮大，這樣，就只需要再次比較樹的一部分就可以找到第二小的值。

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

typedef struct sort_node{
	int key; //待排關(guān)鍵字
	int pos; //此關(guān)鍵字在待排序列中的位置
}SortNode;

int level=1;
SortNode **level_point;
//記錄每一層的關(guān)鍵字容量的連續(xù)空間
int *level_count;
//記錄已經(jīng)排序號(hào)的關(guān)鍵字序列
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){

	//開辟存儲(chǔ)排序序列的容量
	sorted_keys=(int *)malloc(size*sizeof(int));

	//根據(jù)待排序列的數(shù)量確定排序樹的層次
	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++;
	
	//夠著排序樹的內(nèi)存結(jié)構(gòu)，為每一層開辟可以容納一定數(shù)量關(guān)鍵字的內(nèi)存空間
	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層賦值待排序列，并建立排序樹，找到第一次最小的關(guān)鍵字
	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次樹形選擇排序 (關(guān)鍵字 - 關(guān)鍵字在待排表中的位置)："<<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個(gè)最小的數(shù)
	for(int count=1;count<=size-1;count++){
		level_point[0][cur_min_pos].key=MAX_INT;
		
		//找到需要重新比較的兩個(gè)位置
		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;
		}
		//記錄每一次樹形排序的最小值和對(duì)應(yīng)的位置
		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)<<"次樹形選擇排序 (關(guān)鍵字 - 關(guān)鍵字在待排表中的位置)："<<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個(gè)葉子結(jié)點(diǎn)的完全二叉樹，其深度為[logN]+1。因此，除第一次排序需要比較n次以外，其余每一次樹形選擇排序都只需要比較logN次。 因此樹形選擇排序的時(shí)間復(fù)雜度為O(N*logN) 。但是這種排序方法大量額外的空間，一棵n個(gè)葉子結(jié)點(diǎn)的滿二叉樹有2n-1個(gè)結(jié)點(diǎn)。則對(duì)N個(gè)關(guān)鍵字的樹形選擇排序需要近2N左右的結(jié)點(diǎn)。空間復(fù)雜度為 O(2N) 。 該方法也是穩(wěn)定的排序 。

?

樹形選擇排序仍然有很多缺點(diǎn)，比如空間代價(jià)高，需要和無(wú)窮大關(guān)鍵字做比較等。為了彌補(bǔ)，J.willioms在1964年提出了下面的另一種選擇排序——堆排序。

(3) 堆排序

堆的定義如如下：n個(gè)元素的序列{K0 ... K(n-1)}，當(dāng)且僅當(dāng)滿足下關(guān)系時(shí)，稱之為堆。(注: 序列從下標(biāo)0作為第一個(gè)元素開始)

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

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

?

若將此序列對(duì)應(yīng)的一維數(shù)組(序列的內(nèi)存結(jié)構(gòu))看成是一個(gè)完全二叉樹，即Ki 的左孩子是K(2i+1)，右孩子是K(2i+2)。則堆的含義就是，完全二叉樹中所有非終結(jié)點(diǎn)的值均不大于(不小于)其左、右孩子結(jié)點(diǎn)的值。因此，堆頂元素K0就是整個(gè)序列的最小值了。

?

堆排序的算法流程：

首先，將待排序列整理成堆。即從序列的第[n/2]-1個(gè)元素(完全二叉樹最后一個(gè)非終結(jié)點(diǎn))開始，到第0個(gè)結(jié)點(diǎn)為止調(diào)整堆。具體過程見下圖：

然后，輸出堆頂元素K0后，用當(dāng)前堆中最后一個(gè)元素K(n-1)代替堆頂。并將待排序列減少一個(gè)(最后一個(gè)元素已經(jīng)移到了第0號(hào)位置)，接著調(diào)整堆，即將移動(dòng)后的堆頂元素向下調(diào)整(保證小頂堆)。具體過程如下圖：

?

最后，依次循環(huán)下去，直到輸出序列的全部元素為止。

    #include<iostream.h>
/*********************
 * 堆排序 Heap Sort  *   
 *********************/   
class HeapSort{
public:
	//遞增排序
	static void inc_sort(int keys[], int size);
private:
	//創(chuàng)建堆
	static void create(int keys[],int size);
	//調(diào)整堆
	static void adjust(int keys[],int var_size);
	//交換
	static void swap(int keys[],int pos_a,int pos_b);
};
//創(chuàng)建堆
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;
		}
	}
}
//調(diào)整堆
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]<<" "; //ê?3???ò???????Dòμ?×?D??μ
		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);     
}
  

?

堆排序方法對(duì)記錄較少的文件效果一般，但對(duì)于記錄較多的文件還是很有效的。其運(yùn)行時(shí)間主要耗費(fèi)在創(chuàng)建堆和反復(fù)調(diào)整堆上。 堆排序即使在最壞情況下，其時(shí)間復(fù)雜度也為O(N*logN) 。這一點(diǎn)比 快速排序 要好。另外，堆排序所需要的 空間復(fù)雜度為O(1) 。但卻是 不穩(wěn)定排序 。

?

?

【排序結(jié)構(gòu)3】 選擇排序