堆排序详解

以你之姓@ 2022-08-21 03:22 194阅读 0赞

public class HeapSort {
    
    	public static void main(String[] args) {
    		int n = (int)(Math.random()*100);
    		int a[] = new int[n];
    		
    		for(int i=0; i<n; i++){
    			a[i] = (int)(Math.random()*200);
    		}
    		heapSort(a, n);
    		for(int i=0; i<n; i++){
    			System.out.print(a[i]+" ");
    		}
    	}
    	
    	/**
    	 * 堆排序
    	 * 原理：通过维护最大堆 或 最小堆 实现堆排序，最大堆（最小堆）是完全二叉树，要求父节点大于或等于（<=）子节点.
    	 * @param a 待排序数组
    	 * @param len 数组长度
    	 */
    	public static void heapSort(int a[], int len){
    		int lastParentIndex = getParentIndex(len-1);	//最后一个父节点
    		for(int i=lastParentIndex; i>=0; i--){	//从最后一个父节点往前创建最大堆
    			maxHeapify(a, i, len);
    		}
    		
    		
    		//此时已经完成了最大堆的构建，下面进行排序。
    		for(int i=len-1; i>0; i--){	//交换第一个元素（最大的一个）与最后一个元素。
    			a[i] = a[0]^a[i];
    			a[0] = a[0]^a[i];
    			a[i] = a[0]^a[i];
    			maxHeapify(a, 0, i);//维护剩下的元素为最大堆。
    		}
    	}
    	//维护最大堆，保证父节点大于等于子节点
    	public static void maxHeapify(int a[], int index, int len){
    		int leftChildIndex = getLeftChildIndex(index);	//左儿子下标
    		int rightChildIndex = getRightChildIndex(index);	//右儿子下标
    		
    		int maxIndex = index;	//父节点，左儿子，右儿子 中最大的下标，默认是父节点
    		if(leftChildIndex<len && a[leftChildIndex]>a[maxIndex]){	//比较左儿子与最大值
    			maxIndex = leftChildIndex;
    		}
    		if(rightChildIndex<len && a[rightChildIndex]>a[maxIndex]){	//比较右儿子与最大值
    			maxIndex = rightChildIndex;
    		}
    		if(maxIndex != index){	//如果最大值不是父节点的话，交换父节点与最大值。保证了父节点大于等于子节点。
    			a[maxIndex] = a[maxIndex]^a[index];
    			a[index] = a[maxIndex]^a[index];
    			a[maxIndex] = a[maxIndex]^a[index];
    			maxHeapify(a, maxIndex, len);	//交换过后，不能保证交换过后的子节点的下面是最大堆。所以递归
    		}
    			
    	}
    	//获取当前节点的父节点下标
    	public static int getParentIndex(int index){
    		return (index-1)/2;
    	}
    	//获取当前节点的左儿子下标
    	public static int getLeftChildIndex(int index){
    		return index*2+1; 
    	}
    	//获取当前节点的右儿子下标
    	public static int getRightChildIndex(int index){
    		return (index+1)*2;
    	}
    
    }