Java 堆排 (基于数组) 附图解

    堆的定义： 堆是这样一种表，其中每个元素均包含一个键值，表中位置k的元素键值至少与位置2k+1的元素(如果存在)或位置2k+2的元素(如果存在)的键值一样大。

    构建堆的时间复杂度O(n)

    调整堆的时间复杂度O(log2n)

    堆排序时间复杂度O(nlog2n)

    堆排序不稳定

public class HeapSort {
	private void heapify(int arr[],int low, int high){
		int largeIndex;
		int temp=arr[low];
		largeIndex=2*low+1;
		
		while(largeIndex<=high){
			if(largeIndex<high){
				if(arr[largeIndex]<arr[largeIndex+1])
					largeIndex=largeIndex+1;
			}
			if(temp>arr[largeIndex])break;
			else{
				arr[low]=arr[largeIndex];
				low=largeIndex;
				largeIndex=2*low+1;
			}
			arr[low]=temp;
		}
	}
	private void buildHeap(int arr[]){
		int index;
		int length=arr.length;
		for(index=length/2-1;index>=0;index--){
			heapify(arr, index, length-1);
		}
	}
	public void heapSort(int arr[]){
		int lastOutOfOrder;
		int temp;
		int length=arr.length;
		buildHeap(arr);
		for(lastOutOfOrder=length-1;lastOutOfOrder>=0;lastOutOfOrder--){
			temp=arr[lastOutOfOrder];
			arr[lastOutOfOrder]=arr[0];
			arr[0]=temp;
			heapify(arr, 0, lastOutOfOrder-1);
		}
	}
	public static void main(String[] args) {
		HeapSort   hs=new HeapSort();
		int arr[] = { 2, 568, 34, 46, 9, 23, 89, 43, 572, 684, 783, 543 };
		hs.heapSort(arr);
		for (int i = 0; i < 12; i++) {
			System.out.print(arr[i] + ",");
		}
		// 2,9,23,34,43,46,89,543,568,572,684,783,
		
	}
}

 

堆排序的步骤：

1.构建堆

    假定length表示表的长度，令index=length/2-1，那么arr[index]是最后一个非叶节点，

    元素arr[index+1]…arr[legth-1]都是叶节点。

    将包含根节点arr[index]的子树转换为一个堆，然后将包含根节点arr[index-1]的子树转换为一个堆，

    直至把包含根节点arr[0]的数转换成一个堆

2.堆排序

图解：