选择排序：堆排序（不稳定）
堆的定义：n 个元素的序列 (k1, k2, …, kn)，当且仅当满足下列关系：任何一个非终端结点的值都大于等于（或小于等于）它左右孩子的值时，称之为堆。若序列{k1,k2,…,kn}是堆，则堆顶元素（即完全二叉树的根）必为序列中n个元素的最小值（或最大值） 。
可将堆序列看成完全二叉树，则： k2i 是 ki 的左孩子； k2i+1 是 ki 的右孩子。所有非终端结点的值均不大（小）于其左右孩子结点的值。堆顶元素必为序列中 n 个元素的最小值或最大值。
若：ki <= k2i ， ki <= k2i+1，也就是说父小孩大，则为小顶堆（小根堆，正堆），反之，父大孩小，叫大顶堆（大根堆，逆堆）
【堆排序基本思想】：将无序序列建成一个堆，得到关键字最小（大）的记录；输出堆顶的最小（大）值后，将剩余的 n-1 个元素重又建成一个堆，则可得到 n 个元素的次小值；如此重复执行，直到堆中只有一个记录为止，每个记录出堆的顺序就是一个有序序列，这个过程叫堆排序。
堆排序需解决的两个问题：
1、如何由一个无序序列建成一个堆？
2、在输出堆顶元素后，如何将剩余元素调整为一个新的堆？
第二个问题解决方法——筛选：
所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树也成为一个堆。具体是：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。
例： (13, 38, 27, 49, 76, 65, 49, 97)
输出堆顶元素之后，以堆中最后一个元素替代之；
然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换
输出堆顶元素之后，以堆中最后一个元素替代之；
然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换
输出堆顶元素之后，以堆中最后一个元素替代之；
然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换
输出堆顶元素之后，以堆中最后一个元素替代之；
然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换
输出堆顶元素之后，以堆中最后一个元素替代之；
然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换
对深度为 k 的堆，“筛选”所需进行的关键字比较的次数至多为 2(k-1)。
第一个问题解决方法：
从无序序列的第n/2个元素（即无序序列对应的完全二叉树的最后一个内部结点）起，至第一个元素止，进行反复筛选。建堆是一个从下往上进行“筛选”的过程。把原始的序列一一对应的（从左到右，从上到下）建立一个完全二叉树即可，然后建立小顶堆（大顶堆）
1、建堆
2、调整，筛选过程
一趟堆排序完毕，选出了最值和堆里最后一个元素交换，继续
第二趟堆排序完毕，选出了次最值和剩下的元素的最后一个元素交换
第三趟堆排序完毕，重复往复，这样进行堆调整。
第四躺排序完毕，继续
第五躺排序完毕
第六趟排序完毕
最后全部堆排序完毕
这是整个建堆，调整为小顶堆的过程，也就是递增排序。具体是自上而下调整完全二叉树里的关键字，使其成为一个大顶堆（递减排序过程）
操作过程如下：
1、初始化堆：将R[1..n]构造为堆；
2、将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。
对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有节点都进行调整
C#代码实现：
自定义工具类：
参考笔记-016
堆排序类：
/// <summary>
/// 选择类排序
/// </summary>
public class SelectSort
{
//调整推
public static void HeapAdjust(int[] List, int s, int last) //s 为临时堆顶 索引 last 为 堆尾索引
{
int maxTemp = s;
int sLChild = 2 * s; // s 节点的 左孩子索引
int sRChild = 2 * s + 1; // s 节点的 右孩子索引
if (s <= last / 2) //完全二叉树的叶子结点不需要调整，没有孩子
{
if (sLChild <= last && List[sLChild] > List[maxTemp])//如果 当前 结点的左孩子比当前结点记录值大，调整，大顶堆
{
//更新 maxtemp
maxTemp = sLChild;
}
if (sRChild <= last && List[sRChild] > List[maxTemp])//如果 当前 结点的右孩子比当前结点记录值大，调整，大顶堆
{
//更新 maxtemp
maxTemp = sRChild;
}
//如果调整了就交换，否则不需要交换
if (List[maxTemp] != List[s])
{
//不使用中间变量交换两数的值
List[maxTemp] = List[maxTemp] + List[s];
List[s] = List[maxTemp] - List[s];
List[maxTemp] = List[maxTemp] - List[s];
//交换完毕，防止调整之后的新的以 maxtemp 为父节点的子树不是大顶堆，再调整一次
HeapAdjust(List, maxTemp, last);
}
}
}
//建立堆
public static void BuildHeap(int[] List, int last)
{
//明确，具有 n 个结点的完全二叉树（从左到右，从上到下），编号后，有如下关系，设 a 结点编号为 i，若 i 不是第一个结点，那么 a 结点的双亲结点的编号为[i / 2]
//非叶节点的最大序号值为 last / 2
for (int i = last / 2; i >= 0; i--)
{
//从头开始调整为大顶堆
HeapAdjust(List, i, last);
}
}
/// <summary>
/// 3、选择排序：堆排序
/// </summary>
/// <param name="List">数组</param>
public static void HeapSort(int[] List)
{
//建立大顶堆
BuildHeap(List, List.Length-1);
//调整堆
for (int i = List.Length - 1; i >= 1; i--)
{
//将堆顶记录和当前未经排序子序列中最后一个记录相互交换
//即每次将剩余元素中的最大者list[0] 放到最后面 list[i]
List[i] = List[i] + List[0];
List[0] = List[i] - List[0];
List[i] = List[i] - List[0];
//重新筛选余下的节点成为新的大顶堆
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);
}
}
输出结果：
注：
堆排序的时间复杂度和空间复杂度：
对深度为 k 的堆，“筛选”所需进行的关键字比较的次数至多为 2(k-1)；
- 对 n 个关键字，建成深度为
image的堆，所需进行的关键字比较的次数至多 4n；
- 调整“堆顶” n-1 次，总共进行的关键字比较的次数不超过
image，因此，堆排序的时间复杂度为 O(nlogn)，与简单选择排序 O(n^2) 相比时间效率提高了很多。
空间复杂度：S(n) = O(1)
堆排序是一种速度快且省空间的排序方法。相对于快速排序的最大优点：最坏时间复杂度和最好时间复杂度都是 O(n log n)，适用于记录较多的场景（记录较少就不实用），类似折半插入排序，在 T（n）=O（n log n）的排序算法中堆排序的空间复杂度最小为1。
堆排序的稳定性：不稳定排序算法
[参考文献]https://www.cnblogs.com/kubixuesheng/p/4359406.html
选择类排序总结：
