标签:堆排序

堆排序HeapSort

发表于3年前(Dec 24, 2014 10:11:34 AM)  阅读 560  评论 0

分类: Java 算法 排序

标签: buildmaxheap heapsort maxheapify 堆排序 最大堆

堆积排序(Heapsort)是指利用堆积树(堆)这种资料结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素。

堆排序原理有点点复杂,文字我描述不清楚,画图是最有助于理解了的,想深入研究的朋友建议参考算法导论中有关堆排序的描述。

堆排序中有几个重要的过程:Max-Heapify,是用来保持最大堆性质;Build-Max-Heap是用来把一个无序数组建立成最大堆;Heap-Sort则是把一个数组利用最大堆性质进行原地排序。

堆排序的时间复杂度为O(nlog n) ,同合并排序,但相比合并排序他的优点是可以在原数组上实现排序。