43.双面渲染的透明效果

8.堆排序

---

8.1 基础知识

核心思想

堆排序是一种基于二叉堆的排序算法，要把数组当成一个完全二叉树。

首先要构建最大堆，从最后一个非叶子节点逐步往前面的非叶子节点构建最大堆，对大堆就是要保证父节点比子节点大，假如发现父节点没有子节点大，就要把最大的子节点和父节点交换。

构建完最大堆后，根节点就会是值最大的节点了，把根节点和未排序区尾的元素交换，缩小完全二叉树未排序区范围，此时认为丢到未排序区尾的节点已经有序。

重新对缩小后的完全二叉树进行构建构建最大堆，构建完再用根节点和未排序区尾的元素交换，缩小完全二叉树未排序区范围，重复这个过程，直到整个数组有序。

算法步骤

1. 构建最大堆

从最后一个非叶子节点开始，逐步往前调整每个节点，确保每个节点都大于等于其子节点。对于大堆，要保证父节点的值大于其子节点的值。如果发现父节点小于子节点，就交换它们的值，然后继续向下调整。重复上述步骤，直到整个数组构建成最大堆。

2. 堆排序

从最后一个元素开始，将最大堆的根节点与当前元素交换，即将最大值放入数组末尾。缩小堆的范围，排除已经有序的元素，重新调整剩余元素成为最大堆。重复上述步骤，直到整个数组有序。

时间复杂度

堆排序的时间复杂度为O(n log n)，其中n是数组的大小。尽管不如快速排序快，但堆排序不依赖于数据的初始顺序。

空间复杂度

堆排序是原地排序算法，只需要常数级别的额外空间，因此空间复杂度为O(1)。

稳定性

堆排序通常是不稳定的，因为在构建最大堆的过程中，相同值的元素可能发生交换。

适用场景

适用于需要原地排序且对稳定性没有特殊要求的情况。由于不受输入数据分布影响，堆排序在实际应用中具有一定优越性，尤其对于大规模数据集。

代码步骤

1. Heapify函数

调整一个子树为最大堆。接受数组，堆大小，当前子树根节点索引。定义最大索引标识，初始化为当前子树根节点索引。计算得到左右子节点索引，比较子树根节点和左右子节点的元素大小（要检查左右子节点索引是否越界堆大小），记录最大节点值的索引到最大索引标识。如果最大索引标识不是当前子树根节点索引，说明子节点有比当前子树根节点大的元素，交换两者后，递归使用Heapify函数传入数组，堆大小，最大索引确保交换后的子树叶为最大堆。

2. BuildMaxHeap函数

接收一个数组构建最大堆函数。从最后一个非叶子节点开始，逐步向前调用Heapify函数，确保每个节点都大于等于其子节点，完成构建最大堆。

3. HeapSort函数

接收一个数组进行堆排序。调用BuildMaxHeap函数构建最大堆函数。从最后一个元素开始，逐个将最大堆的根节点与当前元素交换，并调用Heapify函数重新调整成最大堆。

总体说明

堆排序是一种强大的排序算法，特别适用于处理大规模数据集。其原地排序和对数据分布的不敏感性使得它在某些场景下成为一个有效的选择。然而，在小规模数据集或对稳定性有较高要求的情况下，可能有更适合的排序算法。

---

8.2 思路框架

static void HeapSort(ref int[] array)
{
    构建最大堆

    从最后一个元素开始往前遍历
    {
        逐个将最大堆的根节点与当前元素交换
        重新调整成最大堆
    }
}

构建最大堆函数
static void BuildMaxHeap(int[] array)
{
    从最后一个非叶子节点开始，逐步向前调整，确保每个节点都大于等于其子节点
}

调整一个子树为最大堆 有可能进行递归
static void Heapify(int[] array, int heapSize, int nowFatherIndex)
{
    初始化当前节点索引为最大值索引，初始化左右字节点索引

    根据左右子节点是否存在（没越界），且值是否大于当前最大值索引所在的节点，更新最大索引值

    如果更新之后最大值索不是当前节点索引，说明更新过最大值索引，交换最大值索引所在元素和当前索引所在元素，并递归的对最大值索引为父节点进行构建最大堆
}

---

8.3 纯净代码

static void HeapSort(ref int[] array)
{
    BuildMaxHeap(array);

    for (int i = array.Length - 1; i > 0; i--)
    {
        SortHelpTool.Swap(ref array[0], ref array[i]);
        Heapify(array, i, 0);
    }
}

static void BuildMaxHeap(int[] array)
{
    for (int i = array.Length / 2 - 1; i >= 0; i--)
    {
        Heapify(array, array.Length, i);
    }
}

static void Heapify(int[] array, int heapSize, int nowFatherIndex)
{
    int biggerIndex = nowFatherIndex;
    int leftSonIndex = 2 * nowFatherIndex + 1;
    int rightSonIndex = 2 * nowFatherIndex + 2;

    if (leftSonIndex < heapSize && array[leftSonIndex] > array[biggerIndex])
    {
        biggerIndex = leftSonIndex;
    }

    if (rightSonIndex < heapSize && array[rightSonIndex] > array[biggerIndex])
    {
        biggerIndex = rightSonIndex;
    }

    if (biggerIndex != nowFatherIndex)
    {
        SortHelpTool.Swap(ref array[nowFatherIndex], ref array[biggerIndex]);
        Heapify(array, heapSize, biggerIndex);
    }
}

require("Lesson01_SortHelpTool")

-- 堆排序函数
function HeapSort(array)
    BuildMaxHeap(array)
    for i = #array, 2, -1 do
        SortHelpTool.Swap(array, 1, i)
        Heapify(array, i - 1, 1)
    end
end

-- 构建最大堆
function BuildMaxHeap(array)
    for i = math.floor(#array / 2), 1, -1 do
        Heapify(array, #array, i)
    end
end

-- 堆调整
function Heapify(array, heapSize, nowFatherIndex)
    local biggerIndex = nowFatherIndex
    local leftSonIndex = 2 * nowFatherIndex
    local rightSonIndex = 2 * nowFatherIndex + 1

    if leftSonIndex <= heapSize and array[leftSonIndex] > array[biggerIndex] then
        biggerIndex = leftSonIndex
    end

    if rightSonIndex <= heapSize and array[rightSonIndex] > array[biggerIndex] then
        biggerIndex = rightSonIndex
    end

    if biggerIndex ~= nowFatherIndex then
        SortHelpTool.Swap(array, nowFatherIndex, biggerIndex)
        Heapify(array, heapSize, biggerIndex)
    end
end

SortHelpTool.PrintArray(SortHelpTool.arrayToSort,"排序前")
HeapSort(SortHelpTool.arrayToSort)
SortHelpTool.PrintArray(SortHelpTool.arrayToSort,"排序后")

---

8.4 带注释代码

using Lesson01_概述;

class Program
{
    static void Main()
    {
        // 输出排序前的数组
        Console.WriteLine("排序前的数组:");
        SortHelpTool.PrintArray(SortHelpTool.arrayToSort);

        // 调用堆排序函数
        HeapSort(ref SortHelpTool.arrayToSort);

        // 输出排序后的数组
        Console.WriteLine("排序后的数组:");
        SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
    }

    // 堆排序函数
    static void HeapSort(ref int[] array)
    {
        // 调用构建最大堆函数
        BuildMaxHeap(array);

        // 从最后一个元素开始，逐个将最大堆的根节点与当前元素交换，并重新调整成最大堆
        for (int i = array.Length - 1; i > 0; i--)
        {
            SortHelpTool.Swap(ref array[0], ref array[i]); // 交换堆顶元素与当前元素
            
            Console.WriteLine("找到最大值放到未排序区末尾后的数组:");
            SortHelpTool.PrintArray(array);
            
            Heapify(array, i, 0); // 调整成最大堆
        }
    }

    // 构建最大堆函数
    static void BuildMaxHeap(int[] array)
    {
        // 从最后一个非叶子节点开始，逐步向前调整，确保每个节点都大于等于其子节点
        for (int i = array.Length / 2 - 1; i >= 0; i--)
        {
            Heapify(array, array.Length, i);
        }
    }

    // 调整一个子树为最大堆 有可能进行递归
    static void Heapify(int[] array, int heapSize, int nowFatherIndex)
    {
        // 初始化当前节点为最大值索引
        int biggerIndex = nowFatherIndex;

        // 计算左子节点的索引
        int leftSonIndex = 2 * nowFatherIndex + 1;

        // 计算右子节点的索引
        int rightSonIndex = 2 * nowFatherIndex + 2;

        // 检查左子节点是否存在且大于当前最大值节点
        if (leftSonIndex < heapSize && array[leftSonIndex] > array[biggerIndex])
        {
            //是最大的话就记录
            biggerIndex = leftSonIndex;
        }

        // 检查右子节点是否存在且大于当前最大值节点
        if (rightSonIndex < heapSize && array[rightSonIndex] > array[biggerIndex])
        {
            //是最大的话就记录
            biggerIndex = rightSonIndex;
        }

        // 如果当前节点不是最大值节点，进行交换并递归调整
        if (biggerIndex != nowFatherIndex)
        {
            // 交换当前节点与最大值节点
            SortHelpTool.Swap(ref array[nowFatherIndex], ref array[biggerIndex]);

            Console.WriteLine($"构建索引为{nowFatherIndex}的父节点为最大堆后的数组:");
            SortHelpTool.PrintArray(array);
            
            // 递归调整子树，即让堆交换后的子树也进行调整最大堆检查，确保交换后的子树仍然是最大堆
            Heapify(array, heapSize, biggerIndex);
        }
    }
}

---

8.5 运行结果

排序前的数组:
5 2 8 1 7 3 10 4 6 9

构建索引为4的父节点为最大堆后的数组:
5 2 8 1 9 3 10 4 6 7
构建索引为3的父节点为最大堆后的数组:
5 2 8 6 9 3 10 4 1 7
构建索引为2的父节点为最大堆后的数组:
5 2 10 6 9 3 8 4 1 7
构建索引为1的父节点为最大堆后的数组:
5 9 10 6 2 3 8 4 1 7
构建索引为4的父节点为最大堆后的数组:
5 9 10 6 7 3 8 4 1 2
构建索引为0的父节点为最大堆后的数组:
10 9 5 6 7 3 8 4 1 2
构建索引为2的父节点为最大堆后的数组:
10 9 8 6 7 3 5 4 1 2
找到最大值放到未排序区末尾后的数组:
2 9 8 6 7 3 5 4 1 10
构建索引为0的父节点为最大堆后的数组:
9 2 8 6 7 3 5 4 1 10
构建索引为1的父节点为最大堆后的数组:
9 7 8 6 2 3 5 4 1 10
找到最大值放到未排序区末尾后的数组:
1 7 8 6 2 3 5 4 9 10
构建索引为0的父节点为最大堆后的数组:
8 7 1 6 2 3 5 4 9 10
构建索引为2的父节点为最大堆后的数组:
8 7 5 6 2 3 1 4 9 10
找到最大值放到未排序区末尾后的数组:
4 7 5 6 2 3 1 8 9 10
构建索引为0的父节点为最大堆后的数组:
7 4 5 6 2 3 1 8 9 10
构建索引为1的父节点为最大堆后的数组:
7 6 5 4 2 3 1 8 9 10
找到最大值放到未排序区末尾后的数组:
1 6 5 4 2 3 7 8 9 10
构建索引为0的父节点为最大堆后的数组:
6 1 5 4 2 3 7 8 9 10
构建索引为1的父节点为最大堆后的数组:
6 4 5 1 2 3 7 8 9 10
找到最大值放到未排序区末尾后的数组:
3 4 5 1 2 6 7 8 9 10
构建索引为0的父节点为最大堆后的数组:
5 4 3 1 2 6 7 8 9 10
找到最大值放到未排序区末尾后的数组:
2 4 3 1 5 6 7 8 9 10
构建索引为0的父节点为最大堆后的数组:
4 2 3 1 5 6 7 8 9 10
找到最大值放到未排序区末尾后的数组:
1 2 3 4 5 6 7 8 9 10
构建索引为0的父节点为最大堆后的数组:
3 2 1 4 5 6 7 8 9 10
找到最大值放到未排序区末尾后的数组:
1 2 3 4 5 6 7 8 9 10
构建索引为0的父节点为最大堆后的数组:
2 1 3 4 5 6 7 8 9 10
找到最大值放到未排序区末尾后的数组:
1 2 3 4 5 6 7 8 9 10

排序后的数组:
1 2 3 4 5 6 7 8 9 10

---

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com