算法思想:堆的定义:source[i]<=source[2*i] && source[i]<= source[2*i+1] 或 source[i]<=source[2*i] && source[i]<= source[2*i+1];
堆排序思想:(1)将待排序序列建成堆;(2)取堆的第一个元素,作为序列的最后一个元素,
并将剩下的元素重新建成堆;(3)重复第二步直到序列结束。
C#实现:
/// <summary> /// 堆排序 /// </summary> /// <param name="source">待排序序列</param> private void HeapSort(int[] source) { for (int i = source.Length / 2; i >= 0;i-- ) { HeapAdjust(source, i, source.Length); } for (int j = source.Length - 1; j >= 0;j-- ) { int temp = source[0]; source[0] = source[j]; source[j] = temp; HeapAdjust(source, 0, j); } } /// <summary> /// 调整为堆 /// </summary> /// <param name="soure">待排序序列</param> /// <param name="i">序列中的第i个元素</param> /// <param name="len">排序序列的长度</param> private void HeapAdjust(int[] soure,int i,int len) { int index = 0; for (int j = i; 2 * j + 1 < len - 1; j=index) { index = 2*j + 1; //左子节点编号 if(index<len-1 && soure[index]<soure[index+1])//找出左子节点和右子节点中较大的。 { index++; } if(soure[index]>soure[j]) //比较根节点和较大子节点,如果根节点较小则交换 { int temp = soure[index]; soure[index] = soure[j]; soure[j] = temp; } } }