堆排序 摘自维基百科

heapSort.java

package main;

import java.util.Arrays;

public class heapSort {
    
	private int[] arr;
    
	public HeapSort(int[] arr){
		this.arr = arr;
	}
	
	public void sort() {
		/*
		 *  第一步将数组堆化
		 */
		int len = arr.length - 1;
		int beginIndex = (len - 1) >> 1;
		for (int i = beginIndex; i>= 0; i--) {
			maxHeapify(i, len);
		}
		
		for (int i = len; i > 0; i--) {
			swap(0, i);
			maxHeapify(0, i - 1);
		}
	}
	
	private void swap(int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
		
	}
	

	private void maxHeapify(int index, int len) {
		int li = (index << 1) + 1; //左子节点索引
		int ri = li + 1; // 右子节点索引
		int cMax = li; //子节点值最大索引
		
		if (li > len) return;
		if (ri <= len && arr[ri] > arr[li]) //先判断左右子节点 哪个较大
			cMax = ri;
		if (arr[cMax] > arr[index]) {
			swap(cMax, index);
			maxHeapify(cMax, len);
		}
	
	}
	
	public static void main(String[] args) {
		int[] arr = new int[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6};  
		new HeapSort(arr).sort();
		System.out.println(Arrays.toString(arr));
	}
}