思想:初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个 堆，这时堆的根节点的数最大。然后将根节点与堆���最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对 它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
2、实例
初始序列：46,79,56,38,40,84
建堆：
交换，从堆中踢出最大数
依次类推：最后堆中剩余的最后两个结点交换，踢出一个，排序完成。
3、java实现
1 package com.sort; 2 //不稳定 3 import java.util.Arrays; 4 5 public class HeapSort { 6 public static void main(String[] args) { 7 int[] a={49,38,65,97,76,13,27,49,78,34,12,64}; 8 int arrayLength=a.length; 9 //循环建堆 10 for(int i=0;i<arrayLength-1;i++){ 11 //建堆 12 buildMaxHeap(a,arrayLength-1-i); 13 //交换堆顶和最后一个元素 14 swap(a,0,arrayLength-1-i); 15 System.out.println(Arrays.toString(a)); 16 } 17 } 18 //对data数组从0到lastIndex建大顶堆 19 public static void buildMaxHeap(int[] data, int lastIndex){ 20 //从lastIndex处节点（最后一个节点）的父节点开始 21 for(int i=(lastIndex-1)/2;i>=0;i--){ 22 //k保存正在判断的节点 23 int k=i; 24 //如果当前k节点的子节点存在 25 while(k*2+1<=lastIndex){ 26 //k节点的左子节点的索引 27 int biggerIndex=2*k+1; 28 //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在 29 if(biggerIndex<lastIndex){ 30 //若果右子节点的值较大 31 if(data[biggerIndex]<data[biggerIndex+1]){ 32 //biggerIndex总是记录较大子节点的索引 33 biggerIndex++; 34 } 35 } 36 //如果k节点的值小于其较大的子节点的值 37 if(data[k]<data[biggerIndex]){ 38 //交换他们 39 swap(data,k,biggerIndex); 40 //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值 41 k=biggerIndex; 42 }else{ 43 break; 44 } 45 } 46 } 47 } 48 //交换 49 private static void swap(int[] data, int i, int j) { 50 int tmp=data[i]; 51 data[i]=data[j]; 52 data[j]=tmp; 53 } 54 }
4、分析
堆排序也是一种不稳定的排序算法。
堆排序优于简单选择排序的原因：