翻译《算法导论》里面的堆排序伪码写的C#堆排序
十二月 14, 2011 at 8:25 下午
—
Easton
/// <summary>
/// 堆排序类
/// </summary>
public class HeapSort
{
/// <summary>
/// 获得父节点下标
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
static int GetParentIndex(int i)
{
return (i >> 1) + 1;
}
/// <summary>
/// 获取左子节点下标
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
static int GetLeftIndex(int i)
{
return (i << 1) + 1;
}
/// <summary>
/// 获取右子节点下标
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
static int GetRightIndex(int i)
{
return (i << 1) + 2;
}
/// <summary>
/// 交换
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
static void exchange(ref int a, ref int b)
{
int temp = a;
a = b;
b = temp;
}
/// <summary>
/// 保持最大堆的特性
/// </summary>
/// <param name="a"></param>
/// <param name="i"></param>
/// <param name="HeapSize"></param>
static void MaxHeapify(int[] a, int i, int HeapSize)
{
//获得左子树节点下标
int l = GetLeftIndex(i);
//获得子树节点下标
int r = GetRightIndex(i);
int largest = i;
if (l < HeapSize && a[l] > a[largest])
largest = l;
if (r < HeapSize && a[r] > a[largest])
largest = r;
//如果i不为根节点,则递归
if (largest != i)
{
exchange(ref a[i], ref a[largest]);
MaxHeapify(a, largest, HeapSize);
}
}
/// <summary>
/// 构建大根堆
/// </summary>
/// <param name="a"></param>
static void BuildMaxHeap(int[] a)
{
for (int i = (a.Length >> 1) - 1; i >= 0; i--)
{
MaxHeapify(a, i, a.Length);
}
}
/// <summary>
/// 堆排序
/// </summary>
/// <param name="a"></param>
public static void Sort(int[] a)
{
//构建大根堆
BuildMaxHeap(a);
for (int i = a.Length - 1; i > 0; i--)
{
exchange(ref a[0], ref a[i]);
MaxHeapify(a, 0, i);
}
}
}
6fc1a9e9-bd36-48ce-9957-6f0867d6fdd4|2|4.5|96d5b379-7e1d-4dac-a6ba-1e50db561b04
Posted in: 技术文章
Tags: 堆排序, C#