c/c++后台开发必知堆与栈的区别( 四 ) 堆（Heap）与栈（Stack）是开发

因此，完成堆排序并没有用到前面说明的插入操作，只用到了建堆和节点向下调整的操作，堆排序的操作如下：
//array:待排序数组， len：数组长度void heapSort(int array[],int len) { //建堆 makeMinHeap(array,len);//最后一个叶子节点和根节点交换，并进行堆调整，交换次数为len-1次 for(int i=len-1;i>0;--i) {//最后一个叶子节点交换array[i]=array[i]+array[0];array[0]=array[i]-array[0];array[i]=array[i]-array[0];//堆调整minHeapFixDown(array, 0, len-i-1);}}（1）稳定性。堆排序是不稳定排序。
（2）堆排序性能分析。由于每次重新恢复堆的时间复杂度为O(logN) ，共N-1次堆调整操作，再加上前面建立堆时N/2次向下调整，每次调整时间复杂度也为O(logN) 。两次操作时间复杂度相加还是O(NlogN) ，故堆排序的时间复杂度为O(NlogN) 。
最坏情况：如果待排序数组是有序的，仍然需要O(NlogN)复杂度的比较操作，只是少了移动的操作；
最好情况：如果待排序数组是逆序的，不仅需要O(NlogN)复杂度的比较操作，而且需要O(NlogN)复杂度的交换操作，总的时间复杂度还是O(NlogN) 。
因此，堆排序和快速排序在效率上是差不多的，但是堆排序一般优于快速排序的重要一点是数据的初始分布情况对堆排序的效率没有大的影响。