30.排序-堆排序
30.1 知识点
堆排序基本原理
构建二叉树和大堆顶规则：
- 构建二叉树。
- 大堆顶调整。
- 堆顶往后方。
- 不停变堆顶。
关键规则：
- 最大非叶子节点：数组长度/2 - 1。
父节点和叶子节点：
- 父节点为i。
- 左节点为2i + 1。
- 右节点为2i + 2。
套路写法：
- 3个函数：
- 1个堆顶比较。
- 1个构建大堆顶。
- 1个堆排序。
- 3个函数：
代码实现
class语句块类 主函数外
// 第一步：实现父节点和左右节点比较
static void HeapCompare(int[] array, int nowFatherIndex, int arrayLength)
{
// 通过传入的索引计算得到对应的左右叶子节点的索引
int leftSonIndex = 2 * nowFatherIndex + 1;
int rightSonIndex = 2 * nowFatherIndex + 2;
// 可能会溢出数组的索引，需要判断
// 用于记录较大数的索引
int biggerIndex = nowFatherIndex;
// 比较左节点，不能溢出
if (leftSonIndex < arrayLength && array[leftSonIndex] > array[biggerIndex])
{
// 认为目前最大的是左节点，记录索引
biggerIndex = leftSonIndex;
}
// 比较右节点，不能溢出
if (rightSonIndex < arrayLength && array[rightSonIndex] > array[biggerIndex])
{
biggerIndex = rightSonIndex;
}
// 如果比较过后，发现最大索引发生变化了，就需要换位置了
if (biggerIndex != nowFatherIndex)
{
// 交换逻辑
int temp = array[nowFatherIndex];
array[nowFatherIndex] = array[biggerIndex];
array[biggerIndex] = temp;
// 通过递归，看是否影响了叶子节点他们的三角关系，biggerIndex就是换了位置的子节点
HeapCompare(array, biggerIndex, arrayLength);
}
}
// 第二步：构建大堆顶
static void BuildBigHeap(int[] array)
{
// 从最大的非叶子节点索引开始，不停往前构建大堆顶
for (int i = array.Length / 2 - 1; i >= 0; i--)
{
HeapCompare(array, i, array.Length);
}
}
// 第三步：结合大堆顶和节点比较，实现堆排序，把堆顶不停往后移动
static void HeapSort(int[] array)
{
// 初始化构建大堆顶
BuildBigHeap(array);
// 执行过后，最大的数肯定就在最上层
// 每一轮确定一个位置
for (int i = array.Length - 1; i > 0; i--)
{
// 直接把堆顶端的数放到最后一个位置即可
int temp = array[0];
array[0] = array[i];
array[i] = temp;
// 重新进行大堆顶调整
HeapCompare(array, 0, i);
}
}
主函数内
// 创建无序数组
int[] arr = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9 };
// 调用堆排序
HeapSort(arr);
// 打印输出
for (int i = 0; i < arr.Length; i++)
{
Console.WriteLine(arr[i]);
// 1
// 2
// 3
// 4
// 5
// 6
// 7
// 8
// 9
}
总结
基本原理：
- 构建二叉树。
- 大堆顶调整。
- 堆顶往后方。
- 不停变堆顶。
套路写法：
- 3个函数：
- 1个堆顶比较。
- 1个构建大堆顶。
- 1个堆排序。
- 3个函数：
重要规则：
- 最大非叶子节点索引：数组长度/2 - 1。
父节点和叶子节点索引：
- 父节点为i。
- 左节点为2i + 1。
- 右节点为2i + 2。
注意：
- 堆是一类特殊的树。
- 堆的通用特点是父节点大于或小于所有子节点。
- 我们并没有真正地把数组变成堆，只是利用了堆的特点来解决排序问题。
30.2 知识点代码
using System;
namespace Lesson29_堆排序
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("堆排序");
//主函数内
#region 知识点二 代码实现
//创建无序数组
int[] arr = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9 };
//调用堆排序
HeapSort(arr);
//打印输出
for (int i = 0; i < arr.Length; i++)
{
Console.WriteLine(arr[i]);
//1
//2
//3
//4
//5
//6
//7
//8
//9
}
#endregion
}
#region 知识点一 堆排序基本原理
//构建二叉树和大堆顶规则
//大堆顶调整
//堆顶往后方
//不停变堆顶
//关键规则
//最大非叶子节点：
//数组长度/2 - 1
//父节点和叶子节点：
//父节点为i
//左节点2i+1
//右节点2i+2
#endregion
//class语句块类 主函数外
#region 知识点二 代码实现
//第一步：实现父节点和左右节点比较
/// <summary>
/// 父节点和左右节点比较函数
/// </summary>
/// <param name="array">需要排序的数组</param>
/// <param name="nowFatherIndex">当前作为父节点的索引</param>
/// <param name="arrayLength">有多少位置没有确定</param>
static void HeapCompare(int[] array, int nowFatherIndex, int arrayLength)
{
//通过传入的索引 计算可得得 它对应的左右叶子节点的索引
int leftSonIndex = 2 * nowFatherIndex + 1;
int rightSonIndex = 2 * nowFatherIndex + 2;
//可能算出来的会溢出数组的索引 我们一会再判断
//用于记录较大数的索引
int biggerIndex = nowFatherIndex;
//先比左 再比右
//比较左节点 不能溢出
if (leftSonIndex < arrayLength && array[leftSonIndex] > array[biggerIndex])
{
//认为目前最大的是左节点 记录索引
biggerIndex = leftSonIndex;
}
//比较右节点 不能溢出
if (rightSonIndex < arrayLength && array[rightSonIndex] > array[biggerIndex])
{
biggerIndex = rightSonIndex;
}
//如果比较过后 发现最大索引发生变化了 那就以为这要换位置了
if (biggerIndex != nowFatherIndex)
{
//交换逻辑
int temp = array[nowFatherIndex];
array[nowFatherIndex] = array[biggerIndex];
array[biggerIndex] = temp;
//通过递归 看是否影响了叶子节点他们的三角关系 biggerIndex就是换了位置的子节点
HeapCompare(array, biggerIndex, arrayLength);
}
}
//第二步：构建大堆顶
static void BuildBigHeap(int[] array)
{
//从最大的非叶子节点索引 开始 不停的往前 去构建大堆顶
for (int i = array.Length / 2 - 1; i >= 0; i--)
{
HeapCompare(array, i, array.Length);
}
}
//第三步：结合大堆顶和节点比较 实现堆排序 把堆顶不停往后移动
static void HeapSort(int[] array)
{
//初始化构建大堆顶
BuildBigHeap(array);
//执行过后 最大的数肯定就在最上层
//每一轮确定一个位置
for (int i = array.Length - 1; i > 0; i--)
{
//直接把 堆顶端的数 放到最后一个位置即可
int temp = array[0];
array[0] = array[i];
array[i] = temp;
//重新进行大堆顶调整
HeapCompare(array, 0, i);
}
}
#endregion
#region 知识点三 总结
//基本原理
//构建二叉树
//大堆顶调整
//堆顶往后方
//不停变堆顶
//套路写法
//3个函数
//1个堆顶比较
//1个构建大堆顶
//1个堆排序
//重要规则
//最大非叶子节点索引：
//数组长度/2 - 1
//父节点和叶子节点索引：
//父节点为i
//左节点2i+1
//右节点2i-1
//注意：
//堆是一类特殊的树
//堆的通用特点就是父节点会大于或小于所有子节点
//我们并没有真正的把数组变成堆
//只是利用了堆的特点来解决排序问题
#endregion
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
