堆排序

1、堆排序

1堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

2、时间复杂度

最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)

3、动态演示

Image text
Image text

4、算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package sort;

public class HeapSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [] a= {99,45,67,12,84,59,32};
		heapSort(a);
		printArr(a);
	}
	
	//堆排序
	public static void heapSort(int[] a) {
		int len=a.length;
		if(len<1) {
			return;
		}
		//构造一个最大堆
		bulidMaxHeap(a);
		
		//循环将最大值与最末位交换，再调整成最大堆
		while(len>0) {
			swap(a,0,len-1);
			len--;
			adjustHeap(a,0);
		}
		
	}
	
	//建立初始大顶堆
	public static void bulidMaxHeap(int[] a) {
		//从最后一个非叶子节点开始
		for(int i=(a.length-1)/2;i>=0;i--) {
			adjustHeap(a,i);
		}
	}
	
	//调整堆
	public static void adjustHeap(int[] a,int i) {
		int max=i;//记录最大值的下标
		
		//如果有左孩子，比较是否大于左孩子
		if(2*i<a.length && a[2*i]>a[max]) {
			max=2*i;
		}
		
		//如果有右孩子，比较大小
		if(2*i+1<a.length && a[2*i+1]>a[max]) {
			max=2*i+1;
		}
		
		//如果父节点不是最大值，则与最大值交换，并递归调整被交换的最大值的位置
		if(max!=i) {
			swap(a,max,i);
			adjustHeap(a,max);
		}
	}
	
	public static void swap(int[] a,int m,int n) {
		int temp=a[m];
		a[m]=a[n];
		a[n]=temp;	
	}

	public static void printArr(int [] a) {
		for(int i=0;i<a.length;i++) {
			System.out.print(a[i]+" ");
		}
	}
}