java中的堆排序算法



package org.sxt.e;

import java.util.Arrays;

/*大顶堆排序，从最后一个节点的父节点（(arr.length-1)/2）大于子节点，往前推，最终把
 * 最大元素放到了第一位，将第一位与最后一位交换，就把最大的放到了最后；
 * 这时把“剩下的元素”在进行上述过程就把第二大的放到了倒数第二位，以此类推
 * 推到头，这时二叉树已经按层次把元素从小到大排好了
 */
public class HeapSort {

	//父节点和两个子节点对比，找出最大的节点
	public static void maxHeap(int[] arr,int size,int index) {
		//左子节点
		int leftNode=2*index+1;
		//右子节点
		int rightNode=2*index+2;
		int max=index;
		//和两个子节点对比，找出最大的节点
		if(leftNode<size&&arr[leftNode]>arr[max]) {//注意：每次要剔除找出的最大元素，元素减少，没有leftNode<size,会发生数组越界
			max=leftNode;
		}
		if(rightNode<size&&arr[rightNode]>arr[max]) {
			max=rightNode;
		}
		//当前元素改变说明需要交换位置
		if(max!=index) {
			int temp=arr[index];
			arr[index]=arr[max];
			arr[max]=temp;
			//交换位置后，可能会影响之前排好的堆，所以之前排好的堆要从此改变处往下调整
			maxHeap(arr,size,max);
		}
	}
	
	public static void heapSort(int[] arr) {
		//开始位置是最后一个非叶子节点，及最后一个节点的父亲
		int start = (arr.length-1)/2;
		//调整为大顶堆(实验说明这个要从最后一个节点的父亲开始往前调,大的元素往上跑)
		for(int i=start;i>=0;i--) {
			maxHeap(arr,arr.length,i);
		}
		//先把数组中第0个和最后一个数交换，再把前面的处理为大顶堆,继续交换
		for(int i=arr.length-1;i>0;i--) {
			int temp =arr[0];
			arr[0]=arr[i];
			arr[i]=temp;
			maxHeap(arr,i,0);//调整因为第0个元素而改变得堆为大顶堆
		}
	}
	
	
	
	
	public static void main(String[] args) {

		int[] arr=new int[] {9,6,8,7,0,1,10,4,2};
		heapSort(arr);
		System.out.println(Arrays.toString(arr));
		
	}
	
	
	
	
	

}
java中的堆排序算法

相关推荐
