簡單選擇排序

選擇排序是一種簡單直觀的排序算法。首先在未排序序列中找到最大（最小）的元素，存放到排序學列的其實位置，然后在剩余的未排序的元素中尋找最小（最大）元素，存放在已排序序列的后面

算法步驟

在未排序序列中找到最大（小）元素，存放在排序序列的起始位置
再從剩余的未排序序列中找到最大（小）元素，然后存放在已排序序列的后面
重復上訴第二步驟，直至排序結束

算法理解

例如對無序表{56，12，80，91，20}采用簡單選擇排序算法進行排序，具體過程為：

第一次遍歷時，從下標為 1 的位置即 56 開始，找出關鍵字值最小的記錄 12，同下標為 0 的關鍵字 56 交換位置：
第二次遍歷時，從下標為 2 的位置即 56 開始，找出最小值 20，同下標為 2 的關鍵字 56 互換位置：
第三次遍歷時，從下標為 3 的位置即 80 開始，找出最小值 56，同下標為 3 的關鍵字 80 互換位置：
第四次遍歷時，從下標為 4 的位置即 91 開始，找出最小是 80，同下標為 4 的關鍵字 91 互換位置：
到此簡單選擇排序算法完成，無序表變為有序表。

代碼實現

#include "iostream"
using namespace std;#define MAX 9
//單個記錄的結構體
typedef struct {int key;
}SqNote;
//記錄表的結構體
typedef struct {SqNote r[MAX];int length;
}SqList;
//交換兩個記錄的位置
void swap(SqNote *a,SqNote *b){int key=a->key;a->key=b->key;b->key=key;
}
//查找表中關鍵字的最小值
int SelectMinKey(SqList *L,int i){int min=i;//從下標為 i+1 開始，一直遍歷至最后一個關鍵字，找到最小值所在的位置while (i+1<L->length) {if (L->r[min].key>L->r[i+1].key) {min=i+1;}i++;}return min;
}
//簡單選擇排序算法實現函數
void SelectSort(SqList * L){for (int i=0; i<L->length; i++) {//查找第 i 的位置所要放置的最小值的位置int j=SelectMinKey(L,i);//如果 j 和 i 不相等，說明最小值不在下標為 i 的位置，需要交換if (i!=j) {swap(&(L->r[i]),&(L->r[j]));}}
}
int main() {SqList *L = new SqList;L->length=8;L->r[0].key=49;L->r[1].key=38;L->r[2].key=65;L->r[3].key=97;L->r[4].key=76;L->r[5].key=13;L->r[6].key=27;L->r[7].key=49;SelectSort(L);for (int i=0; i<L->length; i++) {cout << L->r[i].key << " ";}return 0;
}

代碼實現

13 27 38 49 49 65 76 97

樹形選擇排序

樹形選擇排序（又稱“錦標賽排序”），是一種按照錦標賽的思想進行選擇排序的方法，即所有記錄采取兩兩分組，篩選出較小（較大）的值；然后從篩選出的較小（較大）值中再兩兩分組選出更小（更大）值，依次類推，直到最后選出一個最小（最大）值。同樣可以采用此方式篩選出次小（次大）值等

算法理解

整個排序的過程，可以用一棵具有 n 個葉子結點的完全二叉樹表示。例如對無序表{49，38，65，97，76，13，27，49}采用樹形選擇的方式排序，過程如下：

首先將無序表中的記錄采用兩兩分組，篩選出各組中的較小值（如圖 1 中的（a）過程）；然后將篩選出的較小值兩兩分組，篩選出更小的值，以此類推（如圖 1 中的（b）（c）過程），最終整棵樹的根結點中的關鍵字即為最小關鍵字：

在這里插入圖片描述

圖 1 樹形選擇排序（一）

篩選出關鍵字 13 之后，繼續重復此方式找到剩余記錄中的最小值，此時由于關鍵字 13 已經篩選完成，需要將關鍵字 13 改為“最大值”，繼續重復此過程，如圖 2 所示：圖 2 樹形選擇排序（二）

通過不斷地重復此過程，可依次篩選出從小到大的所有關鍵字。該算法的時間復雜度為O(nlogn)，同簡單選擇排序相比，該算法減少了不同記錄之間的比較次數，但是程序運行所需要的空間較多。

代碼實現

#include "iostream"
using namespace std;
#define N 8
void TreeSelectionSort(int *mData)
{int MinValue = 0;int tree[N * 4]; // 樹的大小int max, maxIndex, treeSize;int i, n = N, baseSize = 1;while (baseSize < n)baseSize *= 2;treeSize = baseSize * 2 - 1;for (i = 0; i < n; i++) {//將要排的數字填到樹上tree[treeSize - i] = mData[i];}for (; i < baseSize; i++) {//其余的地方都填上最小值tree[treeSize - i] = MinValue;}// 構造一棵樹，大的值向上構造for (i = treeSize; i > 1; i -= 2){tree[i / 2] = (tree[i] > tree[i - 1] ? tree[i] : tree[i - 1]);}n -= 1;while (n != -1){max = tree[1];        //樹頂為最大值mData[n--] = max;     //從大到小倒著貼到原數組上maxIndex = treeSize;  //最大值下標while (tree[maxIndex] != max) {maxIndex--;}//找最大值下標tree[maxIndex] = MinValue;while (maxIndex > 1) {if (maxIndex % 2 == 0) {tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex + 1] ? tree[maxIndex] : tree[maxIndex + 1]);}else {tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex - 1] ? tree[maxIndex] : tree[maxIndex - 1]);}maxIndex /= 2;}}
}
int main()
{int a[N] = {49,38,65,97,76,13,27,49};TreeSelectionSort(a);for (int i = 0; i < N; i++) {cout << a[i] << " ";}return 0;
}

運行結果

13 27 38 49 49 65 76 97

堆排序

堆排序 $(He a p sor t)$ 是指利用堆來實現的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。堆排序的平均時間復雜度為 $O (n l o g n)$ 。分為兩種方法：

大頂堆：每個節點的值都大于或等于其子節點的值，在堆排序算法中用于升序排列；
小頂堆：每個節點的值都小于或等于其子節點的值，在堆排序算法中用于降序排列；

在這里插入圖片描述

算法思想

了解了堆的基本性質之后，我們就可以看堆排序的基本思想。

將未排序的序列構造成大（或者小）頂堆，根據堆的性質我們可以找到序列中的最大（或者最小）值
把堆首和堆尾互換，并把堆的大小減 $1$
重復上面的步驟，直到堆的大小為 $1$

在這里插入圖片描述

代碼實現

#include "iostream"
using namespace std;
#define MAX 9
//單個記錄的結構體
typedef struct {int key;
}SqNote;
//記錄表的結構體
typedef struct {SqNote r[MAX];int length;
}SqList;
//將以 r[s]為根結點的子樹構成堆，堆中每個根結點的值都比其孩子結點的值大
void HeapAdjust(SqList * H,int s,int m){SqNote rc=H->r[s];//先對操作位置上的結點數據進行保存，放置后序移動元素丟失。//對于第 s 個結點，篩選一直到葉子結點結束for (int j=2*s; j<=m; j*=2) {//找到值最大的孩子結點if (j+1<m && (H->r[j].key<H->r[j+1].key)) {j++;}//如果當前結點比最大的孩子結點的值還大，則不需要對此結點進行篩選，直接略過if (!(rc.key<H->r[j].key)) {break;}//如果當前結點的值比孩子結點中最大的值小，則將最大的值移至該結點，由于 rc 記錄著該結點的值，所以該結點的值不會丟失H->r[s]=H->r[j];s=j;//s相當于指針的作用，指向其孩子結點，繼續進行篩選}H->r[s]=rc;//最終需將rc的值添加到正確的位置
}
//交換兩個記錄的位置
void swap(SqNote *a,SqNote *b){int key=a->key;a->key=b->key;b->key=key;
}
void HeapSort(SqList *H){//構建堆的過程for (int i=H->length/2; i>0; i--) {//對于有孩子結點的根結點進行篩選HeapAdjust(H, i, H->length);}//通過不斷地篩選出最大值，同時不斷地進行篩選剩余元素for (int i=H->length; i>1; i--) {//交換過程，即為將選出的最大值進行保存大表的最后，同時用最后位置上的元素進行替換，為下一次篩選做準備swap(&(H->r[1]), &(H->r[i]));//進行篩選次最大值的工作HeapAdjust(H, 1, i-1);}
}int main() {SqList *L = new SqList ;L->length=8;L->r[1].key=49;L->r[2].key=38;L->r[3].key=65;L->r[4].key=97;L->r[5].key=76;L->r[6].key=13;L->r[7].key=27;L->r[8].key=49;HeapSort(L);for (int i=1; i<=L->length; i++) {cout << L->r[i].key << " ";}return 0;
}