算法分析（一）堆排序原理及java实现

今天药忘吃喽~ 2022-07-16 02:47 192阅读 0赞

# 一、堆排序思想 #

**以下以大根堆为例：**

**![Center][]**

1、先将初始文件R\[1..n\]建成一个大根堆,此堆为初始的无序区

2、 再将关键字最大的记录R\[1\](即堆顶)和无序区的最后一个记录R\[n\]交换，由此得到新的无序区R\[1..n-1\]和有序区R\[n\]，且满足R\[1..n-1\].keys≤R\[n\].key

3、由于交换后新的根R\[1\]可能违反堆性质，故应将当前无序区R\[1..n-1\]调整为堆。然后再次将R\[1..n-1\]中关键字最大的记录R\[1\]和该区间的最后一个记录R\[n-1\]交换，由此得到新的无序区R\[1..n-2\]和有序区R\[n-1..n\]，且仍满足关系R\[1..n-2\].keys≤R\[n-1..n\].keys，同样要将R\[1..n-2\]调整为堆。

4、……

5、直到无序区只有一个元素为止。

# 二、堆排序步骤 #

1.  构建最大堆。
2.  选择顶，并与第0位置元素交换
3.  由于步骤2的的交换可能破环了最大堆的性质，第0不再是最大元素，需要调用maxHeap调整堆(沉降法)，如果需要重复步骤2

# 三、具体实现细节 #

1. 构建一个最大堆。对于给定的包含有n个元素的数组A\[n\]，构建一个最大堆（最大堆的特性是，某个节点的值最多和其父节点的值一样大。这样，         堆中的最大元素存放在根节点中；并且，在以某一个节点为根的子树中，各节点的值都不大于该子树根节点的值）。从最底下的子树开始，调整           这个堆结构，使其满足最大堆的特性。当为了满足最大堆特性时，堆结构发生变化，此时递归调整对应的子树。   
    2. 堆排序算法，每次取出该最大堆的根节点（因为根节点是最大的），同时，取最末尾的叶子节点来作为根节点，从此根节点开始调整堆，使其满足最大堆的特性。   
    3. 重复上一步操作，直到堆的大小由n个元素降到2个。

伪代码如下：

建堆；

循环（条件：堆不为空）\{

取出堆顶元素；

将最后一个元素移动到堆顶位置；

调整使之再次成为堆；

# 四、演示图如下： #

![Center 1][]

# 五、java实现 #

package com.deppon.tps.module;
    
    public class HeapSortTest {
    	 public static void main(String[] args) {  
    		 Comparable[] data5 = new Comparable[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };  
    	        print(data5);  
    	        sort(data5);  
    	        System.out.println("排序后的数组：");  
    	        print(data5);  
    	    }  
    	 public static void sort(Comparable[] data) {  
    	        // 构建最大堆  
    	        buildMaxHeap(data);  
    	        // 循环，每次把根节点和最后一个节点调换位置  
    	        for (int i = data.length; i > 1; i--) {  
    	            Comparable tmp = data[0];  
    	            data[0] = data[i - 1];  
    	            data[i - 1] = tmp;  
    	  
    	            // 堆的长度减少1，排除置换到最后位置的根节点  
    	            maxHeapify(data, 1, i - 1);  
    	        }  
    	    }  
    	  
    	    // 根据输入数组构建一个最大堆  
    	    private static void buildMaxHeap(Comparable[] data) {  
    	        for (int i = data.length / 2; i > 0; i--) {  
    	            maxHeapify(data, i, data.length);  
    	        }  
    	    }  
    	  
    	    //堆调整，使其生成最大堆  
    	    private static void maxHeapify(Comparable[] data, int parentNodeIndex, int heapSize) {  
    	        // 左子节点索引  
    	        int leftChildNodeIndex = parentNodeIndex * 2;  
    	        // 右子节点索引  
    	        int rightChildNodeIndex = parentNodeIndex * 2 + 1;  
    	        // 最大节点索引  
    	        int largestNodeIndex = parentNodeIndex;  
    	  
    	        // 如果左子节点大于父节点，则将左子节点作为最大节点  
    	        if (leftChildNodeIndex <= heapSize && data[leftChildNodeIndex - 1].compareTo(data[parentNodeIndex - 1]) > 0) {  
    	            largestNodeIndex = leftChildNodeIndex;  
    	        }  
    	  
    	        // 如果右子节点比最大节点还大，那么最大节点应该是右子节点  
    	        if (rightChildNodeIndex <= heapSize && data[rightChildNodeIndex - 1].compareTo(data[largestNodeIndex - 1]) > 0) {  
    	            largestNodeIndex = rightChildNodeIndex;  
    	        }  
    	  
    	        // 最后，如果最大节点和父节点不一致，则交换他们的值  
    	        if (largestNodeIndex != parentNodeIndex) {  
    	            Comparable tmp = data[parentNodeIndex - 1];  
    	            data[parentNodeIndex - 1] = data[largestNodeIndex - 1];  
    	            data[largestNodeIndex - 1] = tmp;  
    	  
    	            // 交换完父节点和子节点的值，对换了值的子节点检查是否符合最大堆的特性  
    	            maxHeapify(data, largestNodeIndex, heapSize);  
    	        }  
    	    }  
    	    public static void print(Comparable[] data) {  
    	        for (int i = 0; i < data.length; i++) {  
    	            System.out.print(data[i] + "\t");  
    	        }  
    	        System.out.println();  
    	    } 
    }

测试结果为：

5 3 6 2 19 4 8 7  
排序后的数组：  
1 2 34 5 6 7 8 9

# 六、堆排序算法分析 #

优点：

1.  堆排序的效率与快排、归并相同，都达到了基于比较的排序算法效率的峰值（时间复杂度为O(nlogn)）
2.  除了高效之外，最大的亮点就是只需要O(1)的辅助空间了，既最高效率又最节省空间，只此一家了
3.  堆排序效率相对稳定，不像快排在最坏情况下时间复杂度会变成O(n^2)），所以无论待排序序列是否有序，堆排序的效率都是O(nlogn)不变（注意这里的稳定特指平均时间复杂度=最坏时间复杂度，不是那个“稳定”，因为堆排序本身是不稳定的）

缺点：（从上面看，堆排序几乎是完美的，那么为什么最常用的内部排序算法是快排而不是堆排序呢？）

1.  最大的也是唯一的缺点就是——堆的维护问题，实际场景中的数据是频繁发生变动的，而对于待排序序列的每次更新（增，删，改），我们都要重新做一遍堆的维护，以保证其特性，这在大多数情况下都是没有必要的。（所以快排成为了实际应用中的老大，而堆排序只能在算法书里面顶着光环，当然这么说有些过分了，当数据更新不很频繁的时候，当然堆排序更好些...）

[Center]: /images/20220716/7ee3ad5f4bf74c68a9899faa28e0812c.png
[Center 1]: /images/20220716/1f5583c32165479da89f98f480a2e63c.png