堆排序

发表于 分类于 ， 阅读次数： 本文字数： 348 阅读时长 ≈ 1 分钟

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。首先以线性时间建立一个大顶堆，然后通过执行N-1次删除堆顶元素(deleteMax)操作来实现元素排序。

代码实现

Java

1
2
3
4
5
6
7
8
private void heapSort() {
     bulidHeap(); //建立一个大顶堆
     for(int i = currentSize; i > 1; i--){
         swapReferences(i, 1);//把堆顶元素放到最后,相当于deleteMax    
         percolateDown(1, i-1);
     }
     System.out.println("排序结果："+ Arrays.toString(arr));
 }

建堆和下滤操作参考上一篇堆的原理和实现。