(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]<<" "; //ê?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);
}
?
堆排序方法對記錄較少的文件效果一般，但對于記錄較多的文件還是很有效的。其運行時間主要耗費在創建堆和反復調整堆上。 堆排序即使在最壞情況下，其時間復雜度也為O(N*logN) 。這一點比 快速排序 要好。另外，堆排序所需要的 空間復雜度為O(1) 。但卻是 不穩定排序 。
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
