1.原地排序，不稳定的，时间复杂度为O（logn） logn为堆的高度；在任何时候数组中只有常数个元素存储在输入数组之外’
调用递归方法实现的堆排序空间复杂度为O（logn），而非递归的才是O（1）
2.值得注意的是：
当数组下标从1开始，即（1<=i<n+1）时，节点 i 的左孩子为 2i,右孩子为 2i+1（右孩子不一定有），i 的父亲为 i/2，最后一个父亲节点为 n/2
当数组下标从0开始，即（0<=i<n）时，节点 i 的左孩子为 2i+1，右孩子为 2i+2(右孩子不一定有），i 的父亲节点为 (i-1)/2，最后一个父亲节点为 (n-1)/2
3.堆排序原理：最大堆节点 i 的值比它的左右字数的值都大 即：父亲节点的值>孩子节点值（最小堆相反）
4.算法步骤：heap_size 最大堆的大小，不是数组元素个数的大小length；
（1）维持最大堆： maxHeapify(int [] a，int i):是对节点i开始维持：首先i处的值要是左右孩子和其本身三个节点值中最大的那个，如果其本身最大则节点i保持最大堆性质，不用动；否则值最大的孩子和节点i交换位置，然后对节点i的新位置(原来孩子处)开始维持最大堆性质（递归）。
该步骤的时间复杂度为O（logn） n为节点数 或者O（h）h为堆高度
（2）建立最大堆：buildMaxHeap(int[] a): 自底向上用maxHeapify对每一个父亲节点（最后面的父亲节点是n-1/2 前面有讲到）建立最大堆，即对n-1/2 到0开始调用maxHeapify函数。当某节点调用maxHeapify维持函数时，它的两个子树已经是最大堆。
该步骤的时间辅助度是对每个父节点调用维持最大堆性质函数，所以时间复杂度为O(nlogn)
（3）堆排序算法heapSort(int[] a)：首先建立最大堆buildMaxHeap(a); 其次从尾节点开始到第二个节点（i从length-1降低到1）交换根节点和尾节点，这里heap_size开始减小；
然后每次对根节点调用维持最大堆函数maxHeapify(a,0).
该算法的时间复杂度是O(nlogn )
5.实现过程：（1）
//4.堆排序 //维持最大堆性质：i表示待维持的节点 public static void maxHeapify(int[] array,int heapSize,int i){ int left=2*i+1; int right=2*i+2;//左右孩子位置，注意 右孩子不一定存在 int largest=i; if(left<heapSize&&array[left]>array[i]){ largest=left; } if(right<heapSize&&array[right]>array[largest]){ largest=right; } if(largest!=i){//节点i处值不是三者中最大的，则交换i和largest两处的节点， int temp=array[i]; array[i]=array[largest]; array[largest]=temp; maxHeapify(array,heapSize,largest);//交换后对孩子处(节点i的新位置)进行维持最大堆性质 } } public static void maxHeapify2(int[] array,int heapSize,int i){//非递归的维持最大堆性质函数 while(true){//循环代替递归 int left=2*i+1; int right=2*i+2; int largest=i; if(left<heapSize&&array[left]>array[i]){ largest=left; } if(right<heapSize&&array[right]>array[largest]){ largest=right; } if(largest!=i){ int temp=array[i]; array[i]=array[largest]; array[largest]=temp; i=largest;//非递归的方式 }else{ break; } } } //建立最大堆:自底向上对每个父节点开始调用维持性质函数，注意是自底向上 public static void buildMaxHeap(int[] array){ if(array==null||array.length<=1)return; int heapSize=array.length; int half=(array.length-1)/2; for(int i=half;i>=0;i--){//自底向上 注意最后一个父节点的位置是n-1/2 maxHeapify(array,heapSize,i); } } //堆排序函数:先建立最大堆，然后交换尾节点和根节点，在对根节点维持最大堆性质 public static void heapSort(int[] array){ if(array==null||array.length<=1) return; buildMaxHeap(array);//建立最大堆 for(int i=array.length-1;i>0;i--){//此处i最小值为1，此时只有根节点和I节点 还可以交换 int temp=array[i]; array[i]=array[0]; array[0]=temp; //System.out.print(temp+"\t"); maxHeapify(array,i,0);//此处heap_size=i } }
（2）建立最大堆函数采用非递归方式：
6.（1）每次把尾节点取出，不做尾节点和根节点交换，直接maxHeapify可以吗？
解答：不可以，举个反例当右子树的值都比左子树大时，50,14,48,8,7,46,40,3,2
