堆排序算法

评分：____________

题目：堆排序算法

一、 实验环境：

1、 硬件环境：个人pc机，

CPU主频：2.66GHz 内存：4GB

2、软件环境：操作系统：Windows 7(旗舰版)

编程语言：java

二、 实验任务解决方案： 1、 算法的流程图。

建立初始堆

1 / 6

生成最小堆

2 / 6

3 / 6

2、 算法实现的关键代码

import static org.junit.Assert.*; import org.junit.Test;

public class TestHeapSort {

public boolean isHeap(int[] a, int i) { int n = a.length; if (i >= n) { return true; }

int left = 2 * i + 1; // 左节点 int right = 2 * i + 2; // 右节点

if (left < n && a[left] > a[i]) { // 比左右都要大，否则不行 return false; }

if (right < n && a[right] > a[i]) { return false; }

return isHeap(a, left) && isHeap(a, right); // 左右子树也是堆 }

public void heapSort(int[] a) {

buildHeap(a); // 首先，建一个堆， 此时a[0] 就是最大的元素 for (int i = a.length - 1; i > 0; i--) { // 每次\"选出\"最大的元素， 共需要进行 n - 1 次

swap(a, 0, i); // 在这之后， i 以及后面的元素都是有序的 heapify(a, 0, i - 1); // 根元素由于被交换过，所以需要进

行一次“调整”, // 让他再变成堆 } }

public void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

public void heapify(int[] a, int i, int j) { int left = i * 2 + 1; int right = i * 2 + 2;

4 / 6

if (left > j) { // 没有左子树？ 那就好了 return; }

int large = left; // large 是大的这个 if (right <= j && a[left] < a[right]) { large = right; } if (a[i] < a[large]) { // 根元素比 large 小？ 交换根和 large swap(a, i, large);

heapify(a, large, j); //此时 large 树 又可能不是堆了, 那就继续努力:) } }

public void buildHeap(int[] a) { int n = a.length;

for (int i = n / 2 - 1; i >= 0; --i) { // n / 2 - 1, 就是最后一个有子节点的元素

heapify(a, i, n - 1); // 偶们从这开始，不断调整，直到整个数组变成堆 } }

public boolean isSorted(int[] ary) {

for (int i = 0; i < ary.length - 1; i++) { if (ary[i] > ary[i + 1]) { return false; } }

return true; }

@Test

public void testIsHeap() {

int[] a = { 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 }; // 就是上述图示数据

assertTrue(isHeap(a, 0)); }

@Test

public void heapSortTest() {

int[] array = {50, 20, 90, 50, 30, 40, 60, 25};

5 / 6

heapSort(array);

assertTrue(isSorted(array)); print(array); }

public void print(int[] array) {

for (int i=0; i3、 算法的计算复杂度分析（最好、最差、平均情况复杂度）：

堆排序的效率到底有多好呢？我们来分析一下。 它的运行时间主要是消耗在初始构

建堆和在重建堆时的反复筛选上。 在构建堆的过程中，因为我们是完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和若有必要的互换，对于每个非终端结点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为O(n)。 在正式排序时，第i次取堆顶记录重建堆需要用O(log2i)的时间（完全二叉树的某个结点到根结点的距离为⌊log2i⌋+1），并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O(nlog2n)。 所以总体来说，堆排序的时间复杂度为O(nlog2n)。由于堆排序对原始记录的排序状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为O(nlog2n)。这在性能上显然要远远好过于冒泡、简单选

2

择、直接插入的O(n)的时间复杂度了。 空间复杂度上，它只有一个用来交换的暂存单元，也算是非常的不错。不过由于记录的比较与交换是跳跃式进行，因此堆排序也是一种不稳定的排序方法。 另外，由于初始构建堆所需的比较次数较多，因此，它并不适合待排序序列个数较少的情况。

4、 综合实验心得体会：

在这次实验中我对堆排序算法有了更好的理解，在做复杂度分析的时候，刚开始没

搞清楚最好、最差的情况的不同，后来查资料给搞定了。然后坐到后面，虽然遇到很多问题，不过通过我们团队的努力，把那些问题解决了！

6 / 6