选择排序——堆排序

快来打我* 2021-12-14 04:43 349阅读 0赞

## 思路 ##

参考：  
[https://download.csdn.net/download/qq\_31567335/10356263][https_download.csdn.net_download_qq_31567335_10356263]

### 什么是堆？ ###

堆是一颗完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。而且堆还必须满足以下性质：父节点大于等于左右子节点（大堆），或者父节点小于等于左右子节点（小堆），后面为了表述方便，在文章中只讨论大堆。

由此可以看出大堆有二个重要的性质：  
1.在堆顶的一定是值最大的元素。  
2.堆的左右子树还是一个堆。

### 用什么样的数据结构存储堆？ ###

表示方式出乎想象的简单。由此图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMxNTY3MzM1_size_16_color_FFFFFF_t_70]  
观察可以发现：i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 \* i + 1和2 \* i + 2。

所以说，只需要将堆按从上到下，从左到右的顺序存储在数组中即可。用上面总结出的公式寻找某个节点的父节点或者子节点。

### 怎么由原始数组构造出堆？ ###

按从右到左，从下到上的顺序对每个节点进行判断。确保此节点大于其左右子节点。如果不满足，就找出左右子节点中最大的，进行交换。当然，交换完成后，子节点可能不再满足堆的性质，所以需要进行递归，直到到达叶子结点。由于最后一个元素的父节点坐标是(n – 1) / 2,大于这个节点的都是叶子节点。所以只需要从(n – 1) / 2开始判断即可。

时间复杂度：n\*lgn。(用极限貌似可以算出来是n,nlgn可以认为是一个粗略但是正确的结果)

### 怎么利用堆进行排序？ ###

构造出堆之后，将第一个元素（最大的元素）和数组最后一个元素进行交换，同时将堆的规模减小1。  
对第一个元素进行一次维护，时间复杂度为lgn。  
重复此步骤，直到每个元素都完成排序。  
总时间复杂度为nlgn。

## 代码 ##

package dataStructureAndAlgorithms;
    
    public class SelectSort_heapSort {
        
    	public static void main(String args[]) {
        
    
    		int[] array = {
         4, 2, 8, 9, 5, 7, 6, 1, 3 };
    
    		System.out.println("未排序数组顺序为：");
    		display(array);
    		System.out.println("-----------------------");
    		sort(array);
    		System.out.println("-----------------------");
    		System.out.println("经过堆排序后的数组顺序为：");
    		display(array);
    	}
    
    	// 堆排序
    	public static void sort(int[] array) {
        
    		int maxIndex = array.length - 1;
    		// 构造堆
    		for (int index = (maxIndex - 1) / 2; index >= 0; index--) {
        
    			buildMaxHeap(array, index, maxIndex);
    		}
    
    		System.out.println("构造完成的堆：");
    		display(array);
    
    		int count = 0;
    		// 确定位置i上的元素
    		for (int i = maxIndex; i >= 1; i--) {
        
    			int temp = array[i];
    			array[i] = array[0];
    			array[0] = temp;
    			buildMaxHeap(array, 0, i - 1);
    
    			System.out.println("经过第" + (count++) + "轮排序后：");
    			display(array);
    		}
    	}
    
    	public static void buildMaxHeap(int[] array, int index, int maxIndex) {
        
    		int left = 2 * index + 1;
    		int right = 2 * index + 2;
    		int largest = index;
    		if (left <= maxIndex && array[largest] < array[left]) {
        
    			largest = left;
    		}
    		if (right <= maxIndex && array[largest] < array[right]) {
        
    			largest = right;
    		}
    
    		if (largest != index) {
        
    			int temp = array[index];
    			array[index] = array[largest];
    			array[largest] = temp;
    			buildMaxHeap(array, largest, maxIndex);
    		}
    	}
    
    	public static void display(int[] array) {
        
    		for (int i = 0; i < array.length; i++) {
        
    			System.out.print(array[i] + " ");
    		}
    		System.out.println();
    	}
    }

## 输出 ##

未排序数组顺序为：
    4 2 8 9 5 7 6 1 3 
    -----------------------
    构造完成的堆：
    9 5 8 3 4 7 6 1 2 
    经过第0轮排序后：
    8 5 7 3 4 2 6 1 9 
    经过第1轮排序后：
    7 5 6 3 4 2 1 8 9 
    经过第2轮排序后：
    6 5 2 3 4 1 7 8 9 
    经过第3轮排序后：
    5 4 2 3 1 6 7 8 9 
    经过第4轮排序后：
    4 3 2 1 5 6 7 8 9 
    经过第5轮排序后：
    3 1 2 4 5 6 7 8 9 
    经过第6轮排序后：
    2 1 3 4 5 6 7 8 9 
    经过第7轮排序后：
    1 2 3 4 5 6 7 8 9 
    -----------------------
    经过堆排序后的数组顺序为：
    1 2 3 4 5 6 7 8 9

[https_download.csdn.net_download_qq_31567335_10356263]: https://download.csdn.net/download/qq_31567335/10356263
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMxNTY3MzM1_size_16_color_FFFFFF_t_70]: /images/20211213/c645f8b28c864262bcc37c95837a6e53.png