堆排序（Heap Sort）

2019-11-06 07:00:27

字体：大中小

来源：转载

供稿：网友

1、算法原理

堆是完全二叉树，堆分为小根堆和大根堆，这里主要讲大根堆，也就是堆的最顶部比其他任何一个子节点都要大（或者等于）。堆的排序复杂度为O(nlogn)。

①时间复杂度

它是不稳定的排序方法。（排序的稳定性是指如果在排序的序列中，存在前后相同的两个元素的话，排序前和排序后他们的相对位置不发生变化）

②算法稳定性

堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。

平均性能： O(N*logN)。

其他性能：由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

堆排序是就地排序，辅助空间为O(1)。

2、实例

/** * @author Hanlin Wang */public class HeapSort { public static void main(String[] args) { int[] data = {7,4,9,5,3,1}; heapSort(data); PRintRes(data); } public static void heapSort(int[] data){ for (int i = 0; i < data.length - 1; i++) { buildMaxHeap(data, data.length - 1 - i); swap(data, 0, data.length - 1 - i); } } public static void buildMaxHeap(int[] data, int lastIndex){ int j; int biggerIndex; for (int i = (lastIndex - 1)/2; i >= 0; i--) { j = i*2 + 1; while (j<=lastIndex) { biggerIndex = j; if (j<lastIndex) { if (data[j] < data[j+1]) { biggerIndex++; } } if (data[i] < data[biggerIndex]) { swap(data, i, biggerIndex); j = biggerIndex*2 + 1; } else { break; } } } } public static void swap(int[] data, int m, int n){ int tmp = data[m]; data[m] = data[n]; data[n] = tmp; } public static void printRes(int[] data){ String txt = ""; for (int i : data) { txt += i + ", "; } String res = txt.substring(0, txt.length() - 2); System.out.println(res); }}

分析：首先，需要先建堆（buildMaxHeap），将最大值放到当前堆的最顶部，最后将最顶部的堆与最后一个数交换位置。每建一次堆，就将每轮建堆的顶部堆放在尾部，最终完成排序。

(lastIndex - 1) / 2 是寻找当前堆的最后一个父节点的公式，只需套用即可。

i*2 + 1 是寻找当前节点的第一个子节点的公式，i*2 + 2 是寻找当前节点的第二个子节点的公式，只需套用即可。

附图GIF图（取自百度百科）：

这里写图片描述