選擇排序：堆排序（不穩(wěn)定）
堆的定義：n 個元素的序列 (k1, k2, …, kn)吁讨，當且僅當滿足下列關系：任何一個非終端結(jié)點的值都大于等于（或小于等于）它左右孩子的值時建丧，稱之為堆。若序列{k1,k2,…,kn}是堆橄维，則堆頂元素（即完全二叉樹的根）必為序列中n個元素的最小值（或最大值） 争舞。
可將堆序列看成完全二叉樹竞川，則： k2i 是 ki 的左孩子委乌； k2i+1 是 ki 的右孩子遭贸。所有非終端結(jié)點的值均不大（懈镌摇）于其左右孩子結(jié)點的值算利。堆頂元素必為序列中 n 個元素的最小值或最大值效拭。
若：ki <= k2i 缎患， ki <= k2i+1，也就是說父小孩大肮街，則為小頂堆（小根堆嫉父，正堆）绕辖，反之仪际，父大孩小树碱，叫大頂堆（大根堆赴恨，逆堆）
【堆排序基本思想】：將無序序列建成一個堆伦连，得到關鍵字最谢蟠尽（大）的記錄歧焦；輸出堆頂?shù)淖钚绢馍。ù螅┲岛蠼⒂浚瑢⑹Ｓ嗟?n-1 個元素重又建成一個堆瓷耙，則可得到 n 個元素的次小值搁痛；如此重復執(zhí)行鸡典，直到堆中只有一個記錄為止彻况，每個記錄出堆的順序就是一個有序序列疗垛，這個過程叫堆排序硫朦。
堆排序需解決的兩個問題：
1泽裳、如何由一個無序序列建成一個堆涮总？
2、在輸出堆頂元素后，如何將剩余元素調(diào)整為一個新的堆谤职？
第二個問題解決方法——篩選：
所謂“篩選”指的是允蜈，對一棵左/右子樹均為堆的完全二叉樹饶套，“調(diào)整”根結(jié)點使整個二叉樹也成為一個堆妓蛮。具體是：輸出堆頂元素之后仔引，以堆中最后一個元素替代之咖耘；然后將根結(jié)點值與左儿倒、右子樹的根結(jié)點值進行比較夫否，并與其中小者進行交換凰慈；重復上述操作微谓，直至葉子結(jié)點豺型，將得到新的堆姻氨，稱這個從堆頂至葉子的調(diào)整過程為“篩選”肴焊。
例： (13, 38, 27, 49, 76, 65, 49, 97)
輸出堆頂元素之后蛀恩，以堆中最后一個元素替代之双谆；
然后將根結(jié)點值與左顽馋、右子樹的根結(jié)點值進行比較，并與其中小者進行交換
輸出堆頂元素之后熊痴，以堆中最后一個元素替代之；
然后將根結(jié)點值與左巾陕、右子樹的根結(jié)點值進行比較鄙煤，并與其中小者進行交換
輸出堆頂元素之后，以堆中最后一個元素替代之亡资；
然后將根結(jié)點值與左、右子樹的根結(jié)點值進行比較旷太，并與其中小者進行交換
輸出堆頂元素之后供璧，以堆中最后一個元素替代之睡毒；
然后將根結(jié)點值與左、右子樹的根結(jié)點值進行比較钠至，并與其中小者進行交換
輸出堆頂元素之后棉钧，以堆中最后一個元素替代之宪卿；
然后將根結(jié)點值與左、右子樹的根結(jié)點值進行比較次绘，并與其中小者進行交換
對深度為 k 的堆，“篩選”所需進行的關鍵字比較的次數(shù)至多為 2(k-1)禾进。
第一個問題解決方法：
從無序序列的第n/2個元素（即無序序列對應的完全二叉樹的最后一個內(nèi)部結(jié)點）起泻云，至第一個元素止宠纯，進行反復篩選婆瓜。建堆是一個從下往上進行“篩選”的過程廉白。把原始的序列一一對應的（從左到右猴蹂，從上到下）建立一個完全二叉樹即可磅轻，然后建立小頂堆（大頂堆）
1弄息、建堆
2、調(diào)整缨称，篩選過程
一趟堆排序完畢型雳，選出了最值和堆里最后一個元素交換纠俭，繼續(xù)
第二趟堆排序完畢朴则，選出了次最值和剩下的元素的最后一個元素交換
第三趟堆排序完畢，重復往復古掏，這樣進行堆調(diào)整槽唾。
第四躺排序完畢豪诲，繼續(xù)
第五躺排序完畢
第六趟排序完畢
最后全部堆排序完畢
這是整個建堆交播，調(diào)整為小頂堆的過程秦士，也就是遞增排序隧土。具體是自上而下調(diào)整完全二叉樹里的關鍵字曹傀，使其成為一個大頂堆（遞減排序過程）
操作過程如下：
1皆愉、初始化堆：將R[1..n]構(gòu)造為堆幕庐；
2异剥、將當前無序區(qū)的堆頂元素R[1]同該區(qū)間的最后一個記錄交換届吁，然后將新的無序區(qū)調(diào)整為新的堆。
對于堆排序潮模，最重要的兩個操作就是構(gòu)造初始堆和調(diào)整堆擎厢，其實構(gòu)造初始堆事實上也是調(diào)整堆的過程动遭，只不過構(gòu)造初始堆是對所有節(jié)點都進行調(diào)整
C#代碼實現(xiàn)：
自定義工具類：
參考筆記-016
堆排序類：
/// <summary>
/// 選擇類排序
/// </summary>
public class SelectSort
{
//調(diào)整推
public static void HeapAdjust(int[] List, int s, int last) //s 為臨時堆頂 索引 last 為 堆尾索引
{
int maxTemp = s;
int sLChild = 2 * s; // s 節(jié)點的 左孩子索引
int sRChild = 2 * s + 1; // s 節(jié)點的 右孩子索引
if (s <= last / 2) //完全二叉樹的葉子結(jié)點不需要調(diào)整厘惦，沒有孩子
{
if (sLChild <= last && List[sLChild] > List[maxTemp])//如果 當前 結(jié)點的左孩子比當前結(jié)點記錄值大，調(diào)整羡玛，大頂堆
{
//更新 maxtemp
maxTemp = sLChild;
}
if (sRChild <= last && List[sRChild] > List[maxTemp])//如果 當前 結(jié)點的右孩子比當前結(jié)點記錄值大稼稿，調(diào)整，大頂堆
{
//更新 maxtemp
maxTemp = sRChild;
}
//如果調(diào)整了就交換讳窟，否則不需要交換
if (List[maxTemp] != List[s])
{
//不使用中間變量交換兩數(shù)的值
List[maxTemp] = List[maxTemp] + List[s];
List[s] = List[maxTemp] - List[s];
List[maxTemp] = List[maxTemp] - List[s];
//交換完畢渺杉，防止調(diào)整之后的新的以 maxtemp 為父節(jié)點的子樹不是大頂堆，再調(diào)整一次
HeapAdjust(List, maxTemp, last);
}
}
}
//建立堆
public static void BuildHeap(int[] List, int last)
{
//明確挪钓，具有 n 個結(jié)點的完全二叉樹（從左到右是越，從上到下），編號后碌上，有如下關系，設 a 結(jié)點編號為 i馏予，若 i 不是第一個結(jié)點天梧，那么 a 結(jié)點的雙親結(jié)點的編號為[i / 2]
//非葉節(jié)點的最大序號值為 last / 2
for (int i = last / 2; i >= 0; i--)
{
//從頭開始調(diào)整為大頂堆
HeapAdjust(List, i, last);
}
}
/// <summary>
/// 3、選擇排序：堆排序
/// </summary>
/// <param name="List">數(shù)組</param>
public static void HeapSort(int[] List)
{
//建立大頂堆
BuildHeap(List, List.Length-1);
//調(diào)整堆
for (int i = List.Length - 1; i >= 1; i--)
{
//將堆頂記錄和當前未經(jīng)排序子序列中最后一個記錄相互交換
//即每次將剩余元素中的最大者list[0] 放到最后面 list[i]
List[i] = List[i] + List[0];
List[0] = List[i] - List[0];
List[i] = List[i] - List[0];
//重新篩選余下的節(jié)點成為新的大頂堆
HeapAdjust(List, 0, i - 1);
Utilit.Print(List, i);
}
}
}
測試用例：
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class _013_SelectSort : MonoBehaviour
{
void Start()
{
int[] a = Utilit.RandArray(20, 10);
int[] b = (int[])a.Clone();
Debug.Log("---------------簡單選擇排序--------------");
SelectSort.SampleSelectSort(a);
//Debug.Log("-------------錯誤簡單選擇排序--------------");
//SelectSort.ErrorSampleSelectSort(b);
Debug.Log("-------------選擇排序:堆排序--------------");
SelectSort.HeapSort(b);
}
}
輸出結(jié)果：
注：
堆排序的時間復雜度和空間復雜度：
對深度為 k 的堆霞丧，“篩選”所需進行的關鍵字比較的次數(shù)至多為 2(k-1)呢岗；
- 對 n 個關鍵字，建成深度為
image的堆，所需進行的關鍵字比較的次數(shù)至多 4n后豫；
- 調(diào)整“堆頂” n-1 次悉尾，總共進行的關鍵字比較的次數(shù)不超過
image，因此挫酿，堆排序的時間復雜度為 O(nlogn)构眯，與簡單選擇排序 O(n^2) 相比時間效率提高了很多。
空間復雜度：S(n) = O(1)
堆排序是一種速度快且省空間的排序方法早龟。相對于快速排序的最大優(yōu)點：最壞時間復雜度和最好時間復雜度都是 O(n log n)惫霸，適用于記錄較多的場景（記錄較少就不實用），類似折半插入排序葱弟，在 T（n）=O（n log n）的排序算法中堆排序的空間復雜度最小為1壹店。
堆排序的穩(wěn)定性：不穩(wěn)定排序算法
[參考文獻]https://www.cnblogs.com/kubixuesheng/p/4359406.html
選擇類排序總結(jié)：
