十大排序算法之堆排序

柔情只为你懂 2024-04-18 22:33 87阅读 0赞

例题：  
对a\[\]=\{3,44,38,5,47,15,36,26,27,2,46,4,19,50,48\}排序  
要求从小到大排列。  
引入新知识：  
这个排序要涉及到数据结构中一个满二叉树的概念  
先说二叉树的概念：  
每个父节点最多拥有两个子节点的树为二叉树  
满二叉树的概念：  
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。  
思路：  
在堆的顶端放置最大的数，且任一个节点的子节点值均小于它  
取出最大值，与当前堆最后一个交换位置，重新排序找出最大值  
重复操作。  
难点：  
如何找出最大值：  
初次遍历整个数组，使堆的左右子节点均小于它，  
每次取出最大值后，重新排列数组。  
![在这里插入图片描述][20190912221635881.gif]  
java代码：

package 日常练习;
    
    import java.util.Arrays;
    
    public class 堆排序 {
    	public static int a[] = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
    
    	public static void main(String[] args) {
    		Sort();
    		System.out.println(Arrays.toString(a));
    	}
    
    	public static void Sort() {
    		if (a == null || a.length <= 1) {
    			return;
    		}
    		int mid = a.length / 2;
    		for (int i = mid; i >= 0; i--) {
    			check(a.length, i); 
    		}
    		for (int i = a.length - 1; i >= 1; i--) {
    			swap(0, i);
    			check(i, 0);
    		}
    	}
    
    	private static void check(int size, int p) {
    		int left = p * 2 + 1;
    		int right = p * 2 + 2;
    
    		int big = p;
    		if (left < size && a[left] > a[p]) {
    			big = left;
    		}
    
    		if (right < size && a[right] > a[big]) {
    			big = right;
    		}
    
    		if (p != big) {
    			swap(p, big); 
    			check(size, big);
    		}
    	}
    
    	public static void swap(int x, int y) {
    		int t = a[x];
    		a[x] = a[y];
    		a[y] = t;
    	}
    }

[20190912221635881.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/a28e5cd022f44b14a367f46ace994781.gif