选择排序：堆排序（不稳定）

堆的定义：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)

image

输出堆顶元素之后，以堆中最后一个元素替代之；

image

然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换

image image

输出堆顶元素之后，以堆中最后一个元素替代之；

image

然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换

image image

输出堆顶元素之后，以堆中最后一个元素替代之；

image

然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换

image

输出堆顶元素之后，以堆中最后一个元素替代之；

image

然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换

image

输出堆顶元素之后，以堆中最后一个元素替代之；

image

然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换

image image

对深度为 k 的堆，“筛选”所需进行的关键字比较的次数至多为 2(k-1)。

---

第一个问题解决方法：

从无序序列的第n/2个元素（即无序序列对应的完全二叉树的最后一个内部结点）起，至第一个元素止，进行反复筛选。建堆是一个从下往上进行“筛选”的过程。把原始的序列一一对应的（从左到右，从上到下）建立一个完全二叉树即可，然后建立小顶堆（大顶堆）

image

1、建堆

image

2、调整，筛选过程

image image image image image

一趟堆排序完毕，选出了最值和堆里最后一个元素交换，继续

image image image

第二趟堆排序完毕，选出了次最值和剩下的元素的最后一个元素交换

image image image

第三趟堆排序完毕，重复往复，这样进行堆调整。

image image

第四躺排序完毕，继续

image image

第五躺排序完毕

image image

第六趟排序完毕

image

最后全部堆排序完毕

image

这是整个建堆，调整为小顶堆的过程，也就是递增排序。具体是自上而下调整完全二叉树里的关键字，使其成为一个大顶堆（递减排序过程）

操作过程如下：

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);

    }

}

---

输出结果：

img.jpg

注：

堆排序的时间复杂度和空间复杂度：

1. 对深度为 k 的堆，“筛选”所需进行的关键字比较的次数至多为 2(k-1)；

2. 对 n 个关键字，建成深度为 image

的堆，所需进行的关键字比较的次数至多 4n；

3. 调整“堆顶” 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

---

选择类排序总结：

img.jpg img.jpg image.png