堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。可以利用数组的特点快速定位指定索引的元素。 堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。 堆分为大根堆和小根堆，是完全二叉树。每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。 堆排序的图解： http://wenku.cyjzzd.com/a/138698##wk-more 堆排序的基本思路： a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆; b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端; c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
public class Heapsort{ //构建最小堆 public static void adjustHeap(int []arr,int i,int length) { int temp=arr[i]; for(int k=2*i+1;k<length;k=k*2+1) { if(k+1<length&&arr[k]<arr[k+1]) { k++; } if(arr[k]>temp) { arr[i]=arr[k]; i=k; }else { break; } } arr[i]=temp; } public static void swap(int []arr,int a,int b) { int temp=arr[a]; arr[a]=arr[b]; arr[b]=temp; } public static void hSort(int []arr) { int i; //从第一个非叶子节点开始调整堆结构 for(i=arr.length/2-1;i>=0;i--){ adjustHeap(arr,i,arr.length); } //交换根元素和第一个元素 for(i=arr.length-1;i>0;i--) { swap(arr, 0, i); adjustHeap(arr, 0, i); } } public static void main(String[] args) { int arr[]= {5,4,9,8,7,6,0,1,3,2}; hSort(arr); for(int a:arr) { System.out.print(a); } } } 运行结果： 0123456789堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。
