经典排序算法之：堆排序

2019-11-08 01:18:34

字体：大中小

来源：转载

供稿：网友

背景及原理

1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams）在1964年共同发明了著名的堆排序算法（ Heap Sort )。堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

算法思路

基本思路：

这里写图片描述上图的左图是堆的构造过程，右图是下沉操作。堆排序的主要操作在第二阶段完成。这里我们将堆最大元素删除然后放入堆缩小后空出的位置中。我们发现，这个过程与选择排序很相似，但是需要的比较次数要少得多。

程序实现：

package algs;public class HeapSort { //堆排序核心算法 public static void sort(Comparable[] pq) { int n = pq.length; //创建堆 for (int k = n/2; k >= 1; k--) sink(pq, k, n); //销毁堆 while (n > 1) { exch(pq, 1, n--);//把找到的最大的数交换到最后。 sink(pq, 1, n);//把第一个数放到合适的位置，构建堆。 } } //下沉 PRivate static void sink(Comparable[] pq, int k, int n) { while (2*k <= n) { int j = 2*k; if (j < n && less(pq, j, j+1)) j++; if (!less(pq, k, j)) break; exch(pq, k, j); k = j; } } //判断大小 private static boolean less(Comparable[] pq, int i, int j) { return pq[i-1].compareTo(pq[j-1]) < 0; } private static void exch(Object[] pq, int i, int j) { Object swap = pq[i-1]; pq[i-1] = pq[j-1]; pq[j-1] = swap; } //打印输出 private static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } System.out.println(); } //测试用例 public static void main(String[] args) { Comparable[] a = new Comparable[] {'B','F','S','R','T','J','D','A','Z','V','Y','H','K','I','P','Q','C','G','N','U','M','E','O'}; System.out.print("排序前："); show(a); System.out.print("排序后："); HeapSort.sort(a); show(a); }}

[程序输出]

排序前：B F S R T J D A Z V Y H K I P Q C G N U M E O 排序后：A B C D E F G H I J K M N O P Q R S T U V Y Z

上一篇：文章标题

下一篇：华为机试在线训练-牛客网（34）参数解析