常见Java问题及笔试题（三十四）——堆排序代码的实现（含简单数学证明）「建议收藏」

在看代码之前，我们首先看一个数学证明，由于堆排序针对的都是完全二叉树，所以本文的证明都是针对完全二叉树的证明。其实也很简单。只是网上都没有相关证明，都是一笔带过，所以我就写一下，基本上算是初中证明题：

我们知道在一棵非叶子节点，它的节点编号（编号从1开始）如果是n的话，那么它的左孩子节点编号是2n，如果有右孩子的话，那么右孩子的编号是2n+1.还有一个证明就是针对完全二叉树中度为2的结点数和叶子节点的数目的关系。

由于完全二叉树的度为1的结点最多只有一个，下面第二个证明没有考虑度为1的结点，如果考虑的话，结果还是一样的。只是把n1=1带进去计算就行。

证明结点关系

特别说一下，数组中下边从零开始，略有不同，但是不影响做题！！！

堆排序实际上利用堆的性质来进行排序的一种方法。我们知道堆分为大顶堆和小顶堆，分别对应从小到大和从大到小的排序两种方式。

堆实际上是一棵完全二叉树

思路就很简单了，网上说什么的都有，我自己的理解就是：利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。

操作过程如下：

1)初始化堆：将R[1..n]构造为堆；

2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。

因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。

代码如下：

public class HeapSort {

/**

* 第一步：构造堆 ：所有的叶子节点都是堆–>(数组长度+1)/2 = 叶子节点的个数(从后往前数)

*/

public static void main(String[] args) {

int[] array = new int[] { 3, 5, 7, 2, 6, 1, 3, 8, 4 };

heapSort(array);

System.out.println(“\nresult\n”);

print(array);

}

public static void heapAdjust(int[] array, int parent, int length) {

int temp = array[parent];

int child = 2 * parent + 1;

while (child < length) {

// 找最大子节点

if (child + 1 < length && array[child] < array[child + 1]) {

child = child + 1;

}

if (temp >= array[child]) {

break;

}

// 小于则交换

array[parent] = array[child];

array[child] = temp;

// continue

parent = child;

child = 2 * parent + 1;

}

}

public static void heapSort(int[] list) {

// 组装堆–>取一半就行了,因为叶子节点本来就占了一半(相关证明文中已经给出)

for (int i = (list.length) / 2; i >= 0; i–) {

heapAdjust(list, i, list.length – 1);

}

System.out.println(“\nheap\n”);

print(list);

// 倒叙取根

for (int i = list.length – 1; i >= 0; i–) {

// 交换根和最后元素

int temp = list[i];

list[i] = list[0];

list[0] = temp;

// 调整剩余元素为堆,此时数组最后一个数已被剔除，所以只需要传递i即可

heapAdjust(list, 0, i);

// 打印出每一步执行完，数组的变化

System.out.println(“\nthe ” + (list.length – i) + ” step:\n”);

print(list);

}

}

private static void print(int[] array) {

for (int i : array) {

System.out.print(i + “,”);

}

System.out.println();

}

}

运行结果如下：