@22221cjp
2016-09-13T13:38:05.000000Z
字数 380
阅读 1121
堆排序
技术
构建堆
堆是一个完全二叉树，给定一个整形数组a[]={16,7,3,20,17,8}，对其进行堆排序。先构建堆
20和16交换后导致16不满足堆的性质，因此需重新调整
这样就得到了初始堆。
即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。
构建堆的时间复杂度：
间堆的时间复杂度是O(N)
取堆顶元素，然后调堆的时间复杂度是logN
堆排序的时间复杂度为：
log1+log2+...+logN=log N! 约等于 NlogN
堆排序总的时间复杂度是两个加起来，所以是O(nlogn)
参考：http://blog.csdn.net/xiaoxiaoxuewen/article/details/7570621/
