java 数据结构之堆排序（HeapSort）详解及实例
1堆排序
堆是一种重要的数据结构，分为大根堆和小根堆，是完全二叉树,底层如果用数组存储数据的话，假设某个元素为序号为i(Java数组从0开始,i为0到n-1),如果它有左子树，那么左子树的位置是2i+1，如果有右子树，右子树的位置是2i+2，如果有父节点，父节点的位置是(n-1)/2取整。最大堆的任意子树根节点不小于任意子结点，最小堆的根节点不大于任意子结点。
所谓堆排序就是利用堆这种数据结构的性质来对数组进行排序，在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的性质可知，最大的值一定在堆顶。堆排序一种不稳定的排序算法，其时间复杂度为O(nlogn)。
2算法思想
（1）构建最大堆；
（2）选择顶，并与第0位置元素交换；
（3）由于步骤（2）的的交换可能破环了最大堆的性质，即第0位置的元素不再是最大元素，则需要调用maxHeap调整堆(沉降法)，根据实际情况重复步骤（2）。
堆排序中最重要的算法就是maxHeap，该函数假设一个元素的两个子节点都满足最大堆的性质(即左、右子树都是最大堆)，只有根元素可能违反最大堆性质，那么把该元素以及左右子节点的最大元素找出来，如果该元素已经最大，那么整棵树都是最大堆，程序退出，否则交换根元素与最大元素的位置，继续调用maxHeap构建最大元素所在的子树。
3Java代码
publicclassHeapSort{
publicstaticvoidmain(String[]args){
int[]arr={3,2,1,0,-1,-2,-3};
System.out.println("Beforeheap:");
printArray(arr);
heapSort(arr);
System.out.println("Afterheapsort:");
printArray(arr);
}
publicstaticvoidheapSort(int[]arr){
if(arr==null||arr.length<=1){
return;
}
buildMaxHeap(arr);//构建最大堆
for(inti=arr.length-1;i>=1;i--){
exchangeElements(arr,0,i);//交换堆顶和第0位置元素
maxHeap(arr,i,0);//因为交换元素后，有可能违反堆的性质，所以沉降元素
}
}
privatestaticvoidbuildMaxHeap(int[]arr){//构建最大堆
if(arr==null||arr.length<=1){
return;
}
inthalf=arr.length/2;
for(inti=half;i>=0;i--){
maxHeap(arr,arr.length,i);
}
}
privatestaticvoidmaxHeap(int[]arr,intheapSize,intindex){
intleft=index*2+1;//左子树上的元素
intright=index*2+2;//右子树上的元素
intlargest=index;//初始化最大元素
if(leftarr[index]){
largest=left;
}
if(rightarr[largest]){
largest=right;
}
if(index!=largest){//判断根元素是否为最大元素
exchangeElements(arr,index,largest);
maxHeap(arr,heapSize,largest);
}
}
publicstaticvoidprintArray(int[]arr){//打印数组
System.out.print("{");
for(inti=0;i
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！