趁考试周,总结一下这学期所学的数据结构与算法知识。这次先按考试内容来总结,暑假进行完善。
堆排序(C#实现)
背景
堆排序,就是利用堆这种数据结构来实现排序功能。本文介绍堆排序的基本原理及代码实现。
此外,本文只介绍升序排序的情况。
基本理论
堆分为大根堆和小根堆,当满足双亲结点均大于孩子结点时,称为大根堆;反之,若双亲结点均小于孩子结点时,称为小根堆。
实现过程:
给定一个含n个元素的序列,构建为大根堆,输出堆顶元素(实质上是将堆顶元素置换到序列尾部),对剩下的 n − 1 n-1 n−1元素构建大根堆,输出堆顶元素,如此反复,得到升序排序序列。
核心问题
堆排序的核心问题有两个,一个是如何建堆,另一个是输出堆顶元素后重新构建大根堆。
- 初始建堆
- 调整新堆
代码实现:
C#">/// <summary>
/// 二叉堆的重构(针对于已构建好的二叉堆首尾互换之后的重构)
/// </summary>
/// <param name="Key"></param>
/// <param name="j">根结点j</param>
/// <param name="vCount">结点数</param>
public void Restore(int[] Key, int j, int vCount)
{
while (j <= vCount / 2) // 保证根结点有子树
{
//找出左右儿子的最大值
int m = (2 * j + 1 <= vCount && Key[2 * j + 1] > Key[2 * j]) ? 2 * j + 1 : 2 * j;
if (Key[m] > Key[j])
{
int temp = Key[m];
Key[m] = Key[j];
Key[j] = temp;
j = m;
}
else
{
break;
}
}
}
/// <summary>
/// 堆排序
/// </summary>
/// <param name="Key">待排序数组</param>
public void HeapSort(int[] Key)
{
int vCount = Key.Length;
int[] tempKey = new int[vCount + 1];
// 元素索引从1开始
for (int i = 0; i < vCount; i++)
{
tempKey[i + 1] = Key[i];
}
// 初始数据建堆(从含最后一个结点的子树开始构建,依次向前,形成整个二叉堆)
for (int i = vCount / 2; i >= 1; i--)
{
Restore(tempKey, i, vCount);
}
// 不断输出堆顶元素、重构堆,进行排序
for (int i = vCount; i > 1; i--)
{
int temp = tempKey[i];
tempKey[i] = tempKey[1];
tempKey[1] = temp;
Restore(tempKey, 1, i - 1);
}
//排序结果
for (int i = 0; i < vCount; i++)
{
Key[i] = tempKey[i + 1];
}
}