阅读本文大概需要4分钟
其他
学会堆排序只需要几分钟
之前我写过一篇数据结构的文章：堆其实是个很简单的数据结构。
堆排序，顾名思义，是要借助堆这种数据结构来实现对数据项的排序。在堆这种数据结构中，节点大于或等于自己的子节点，正因为堆有这种特点，所以我们可以将待排序的数据项依次添加到堆中，然后再依次取出根节点。
从堆中取出来的数据项是从大到小排列的，因为根节点永远是最大的，而堆中永远是取根节点。下面来看下堆排序的具体实现（也可以参考堆这个数据结构的代码）
public class HeapSort {
private int[] array;
private int currentIndex;
private int maxSize;
public HeapSort(int size) {
maxSize = size;
array = new int[maxSize];
currentIndex = 0;
}
//插入数据项，并排好序
public void insertSort(int[] source) {
for(int i = 0; i < source.length; i++) {
array[currentIndex] = source[i]; //插入到节点尾
tickedUp(currentIndex++); //向上重新排好序，使得满足堆的条件
}
}
private void tickedUp(int index) {
int parentIndex = (index - 1) / 2; //父节点的索引
int temp = array[index]; //将新加的尾节点存在temp中
while(index > 0 && array[parentIndex] < temp) {
array[index] = array[parentIndex];
index = parentIndex;
parentIndex = (index - 1) / 2;
}
array[index] = temp;
}
//取出最大值
public int getMax() {
int maxNum = array[0];
array[0] = array[--currentIndex];
trickleDown(0);
return maxNum;
}
private void trickleDown(int index) {
int top = array[index];
int largeChildIndex;
while(index < currentIndex/2) { //while node has at least one child
int leftChildIndex = 2 * index + 1;
int rightChildIndex = leftChildIndex + 1;
//find larger child
if(rightChildIndex < currentIndex && //rightChild exists?
array[leftChildIndex] < array[rightChildIndex]) {
largeChildIndex = rightChildIndex;
}
else {
largeChildIndex = leftChildIndex;
}
if(top >= array[largeChildIndex]) {
break;
}
array[index] = array[largeChildIndex];
index = largeChildIndex;
}
array[index] = top;
}
}算法分析：堆中插入和取出的时间复杂度均为 O(logN)，所以堆排序算法的时间复杂度为 O(logN)，但是堆排序也需要额外的和待排序序列大小相同的存储空间。其空间复杂度为 O(N)。
这世上天才很少，懒蛋却很多，你若对得起时间，时间便对得起你。关注我们，利用碎片时间学习，每天进步一点点。
这里不仅只有技术