很早就学习了堆排序但当时没有用代码实现，现在再去想实现已经忘光光啦┑(￣Д ￣)┍，于是就去网上搜了一番，发现没有一篇我能认真看完的文章，没办法就是没耐心，就是笨呗。。。好了，言归正传=￣ω￣=
了解概念
首先明白什么是堆，什么是完全二叉树，什么是大顶堆，相信百度一下很容易理解o(^▽^)o。
堆可以用数组来存储，如下图，数组 a[0，...，9] 表示一个堆在数组中的存储模式。数组中下标为i的节点的子节点下标分别为2*i+1、2*i+2，下标为j的子节点的父节点下标为(j-1)/2。
算法描述
将待排序数组构建成一个大顶堆，也就是变换原始数组中元素的位置，使之满足大顶堆的定义。
将堆顶节点与堆中末尾节点交换，也就是数组的首尾元素交换，此时末尾节点已为最大元素，考虑剩余节点形成的堆。
将最新的堆重新构造成大顶堆。
重复第2步、第3步直到堆中节点全部输出。
算法实现
public class HeapSort {
public static void heapSort(int[] array) {
array = buildMaxHeap(array); //初始建堆，array[0]为第一趟值最大的元素
for (int i = array.length - 1; i >= 1; i--) {
int temp = array[0]; //将堆顶元素和堆底元素交换，即得到当前最大元素正确的排序位置
array[0] = array[i];
array[i] = temp;
adjustHeap1(array, 0, i); //整理，将剩余的元素整理成大顶堆
}
}
//自下而上构建大顶堆：将array看成完全二叉树的顺序存储结构
private static int[] buildMaxHeap(int[] array) {
//从最后一个节点array.length-1的父节点(array.length-1-1)/2开始，直到根节点0，反复调整堆
for(int i=(array.length-2)/2;i>=0;i--){
adjustHeap1(array, i, array.length);
}
return array;
}
//自上而下调整大顶堆(非递归)
private static void adjustHeap1(int[] array, int k, int length) {
int temp = array[k]; //堆顶节点
for (int i = 2*k+1; i <= length - 1; i = 2*i+1) { //i为初始化为节点k的左孩子，沿节点较大的子节点向下调整
if (i+1< length && array[i] < array[i + 1]) { //如果左孩子小于右孩子
i++; //则取右孩子节点的下标
}
if (temp >= array[i]) { //堆顶节点 >=左右孩子中较大者，调整结束
break;
} else { //根节点 < 左右子女中关键字较大者
array[k] = array[i]; //将左右子结点中较大值array[i]调整到双亲节点上
k = i; //【关键】修改k值，以便继续向下调整
}
}
array[k] = temp; //被堆顶结点的值放人最终位置
}
//自上而下调整大顶堆(递归)
private static void adjustHeap2(int[] array, int k, int length) {
int k1=2*k+1;
if(k1
k1++;
}
if(k1>length-1||array[k]>=array[k1]){
return;
}else{
int temp = array[k]; //将堆顶元素和左右子结点中较大节点交换
array[k] = array[k1];
array[k1] = temp;
adjustHeap2(array,k1,length);
}
}
public static void main(String[] args) {
int[] a = {87,45,78,32,17,65,53,9,122,133};
heapSort(a);
System.out.println(Arrays.toString(a));
}
}
算法复杂度
堆排序时间计算分两部分，构建堆时间复杂度O(n)，调整堆时间复杂度O(nlogn)，总的时间复杂度O(nlogn)，堆排序为就地排序，空间复杂度O(1)。
