一天一算法（3）：堆排序

原理

推荐去看这个教程，讲的很清晰明了 堆排序

代码

这是我通过理解原理后写的代码：

public static void HeapSort(long []a,int length) { long k; int nowindex = length / 2 - 1;//找出最后一个非叶子节点,这是一个公式 int lastIndex = nowindex; int index; while (length / 2 - 1 >= 0) { while (nowindex >= 0) { ChangeValue(a, nowindex, length); index = nowindex+1; while (index <=lastIndex) { ChangeValue(a, index, length); index++; } nowindex--; } k = a[0]; a[0] = a[length - 1]; a[length - 1] = k; length--; lastIndex = length / 2 - 1; nowindex = 0; } } //交换值，使其满足大顶堆 public static void ChangeValue(long []a,int i,int length) { int num = i*2+1, j=i,k=num; long max=a[i]; while ( num-k <=1 && num <=length - 1) { if (a[num] > max) { max = a[num]; j = num; } num++; } a[j] = a[i]; a[i] = max; }