http://www.cnblogs.com/hapjin/p/5518921.html-阿里云开发者社区

http://www.cnblogs.com/hapjin/p/5518921.html

2017-10-12 1391

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

一，堆排序介绍

堆是一个优先级队列，对于大顶堆而言，堆顶元素的权值最大。将待排序的数组建堆，然后不断地删除堆顶元素，就实现了排序。关于堆，参考：数据结构--堆的实现之深入分析

下面的堆排序算法将数组中的元素从小到大排序，用大顶堆来实现。

二，堆排序算法分析

现给定了一维数组，需要将数组中的元素使用堆排序。首先，得创建一个堆，可以在这个给定的一维数组上建堆。对N个元素建堆的时间复杂度为O(N)

堆排序具体的细节实现有两种方式：一种方式是将堆顶元素删除后，放到一个辅助数组中，然后进行堆调整使之成为一个新。继续删除堆顶元素，直至将堆中所有的元素都出堆，此时排序完成。这种方式需要一个额外的辅助空间O(N)

另一种方式是：将每次删除的堆顶元素放到数组的末尾。因为，对于堆的基本操作 delMin/delMax 而言（delMin针对的是小顶堆，delMax针对的是大顶堆，原理一样）是将堆中的最后一个元素替换堆顶元素，然后向下进行堆调整。因此，可以利用这个特点将每次删除的堆顶元素保存在数组末尾，当所有的元素都出堆后，数组就排好序了。这种方式不需要额外的辅助空间，空间复杂度为O(1)

三，堆排序算法实现

 1 public class HeapSort {
 2     
 3     public static <T extends Comparable<? super T>> void heapSort(T[] arr){
 4         //build heap
 5         for(int i = arr.length/2 - 1; i >= 0; i--)
 6             percDown(arr, i, arr.length);
 7         
 8         
 9         for(int i = arr.length - 1; i >= 0; i--)
10         {
11             swapReference(arr, 0, i);//delete Max
12             
13             percDown(arr, 0, i);// 从根开始向下堆调整
14         }
15     }
16     
17     private static <T extends Comparable<? super T>> void swapReference(T[] arr, int from, int to){
18         T tmp;
19         tmp = arr[from];
20         arr[from] = arr[to];
21         arr[to] = tmp;
22     }
23     
24     //求解 i 的左孩子
25     private static int leftChild(int i){
26         return 2*i + 1;
27     }
28     
29     /**
30      * 
31      * @param arr 存储堆的一维数组
32      * @param i 从 i 位置开始进行向下堆调整
33      * @param n 堆中元素的个数(不是数组的长度)
34      */
35     private static <T extends Comparable<? super T>> void percDown(T[] arr, int i, int n){
36         int child;
37         T tmp;//保存当前待调整的结点，当找到了合适的位置后，需要将之放入到合适位置，以保持堆序性质
38         
39         for(tmp = arr[i];  leftChild(i) < n; i = child)
40         {
41             child = leftChild(i);
42             if(child != n-1 && arr[child].compareTo(arr[child+1]) < 0)
43                 child++;//右孩子更大
44             if(tmp.compareTo(arr[child]) < 0)
45                 arr[i] = arr[child];//父节点下移
46             else
47                 break;//父节点比左右孩子都大时,不需要再向下移动了
48         }
49         arr[i] = tmp;//将节点放入合适的位置
50     }
51     
52     //for test purpose
53     public static void main(String[] args) {
54         Integer[] arr = {31,41,59,26,53,58,97};
55         heapSort(arr);
56         for (Integer i : arr) {
57             System.out.print(i + " ");
58         }
59     }
60 }