堆排序算法
堆排序算法： 是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
将待排序的序列构造成一个大顶堆(从大到小排要构造成小顶堆)。此时，整个序列的最大值就是堆顶的根节点，将他和末尾元素交换，然后将剩余的length-1个节点序列重新构造成新的堆。重复执行，便能得到一个有序序列。
堆的操作： 在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：
最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
Java代码实现 ↓↓↓↓↓↓↓
/***
* 堆排序算法
*/
public class HeapSort {
static void heapSort(int []a,int len){
int i;
/**把a[]构造成一个大顶堆**/
for(i=len/2;i>=0;i--){
HeapAdjust(a,i,len);
}
for(i=len;i>0;i--){
/**交换堆顶最大元素和堆尾最小元素**/
swap(a,0,i);
/**把交换后的堆a[0,i-1]，再次构造成大顶顶，使堆顶元素为最大值**/
HeapAdjust(a,0,i-1);
}
}
static void HeapAdjust(int []a,int start,int len){
int temp,j;
temp=a[start];
/**从index最大的有孩子的节点开始筛选，堆排**/
for(j=2*start; j<=len; j*=2){
/**是index=j的元素为较大的元素**/
if(j<len&&a[j]<a[j+1])
j++;
if(temp>=a[j])
break;
/**将较大元素赋值给父节点**/
a[start]=a[j];
start=j;
}
a[start]=temp;
}
static void swap(int a[],int low,int high){
int temp=a[low];
a[low]=a[high];
a[high]=temp;
}
public static void main(String []args){
int[] b = {97, 58, 3, 12, 88, 77, 101, 7, 22, 33, 44, 8, 66, 22};
heapSort(b, b.length - 1);
for(int w:b)
System.out.print(" "+w);
}
}
运行结果 ↓↓↓↓↓↓↓
