堆排序（Heap Sort），是由罗伯特·弗洛伊德（Robert W.Floyd）和威廉姆斯（J.Williams）于1964年提出的一种基于堆结构的排序方法。直接选择排序在 n n n 个元素中，选出关键字最小（最大）的记录需要 O ( n ) O(n) O(n) 的时间。而利用堆这种数据结构所设计的一种排序算法，小根堆（大根堆）选出关键字最小（最大）的记录只需要 O ( l o g n ) O(logn) O(logn) 的时间。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点
在堆排序过程中，存在大跨度的数据移动，是一种不稳定的排序算法
堆分为两种
- 大根堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列
- 小根堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列
算法步骤
- 由存储于数组中的初始序列，建成一个大根堆（小根堆）
- 将堆顶的最大（或最小）元素与序列中最后一个记录交换，最大（或最小）元素放在数组末尾的有序段中
- 将序列中除末尾的有序段之外的剩余记录重新调整为大根堆（小根堆）
- 反复执行步骤2、3，共 n − 1 n-1 n−1次，若初始建立的是大根堆，则得到一个递增序列；若初始建立的是小根堆，则得到一个递减的序列
测试用例： 使用堆排序算法将数组 { 36，80，45，66，22，9，36，16 } 进行升序排序
代码实现
public int[] siftDown(int[] nums, int position, int size){
int child;
int temp = nums[position]; // 将该非叶子节点值保存
// 循环遍历当前非叶子节点的子节点,实质上是遍历该非叶子节点的所有属于非叶子节点的子节点
for ( ; position * 2 + 1 < size; position = child){
child = position * 2 + 1; // 获取当前非叶子节点的左孩子节点
if (child != size - 1 && nums[child + 1] > nums[child]) // 如果右孩子节点的值 > 左孩子节点的值,选取大者
child++; // 定位较大孩子节点
if (nums[child] > temp) nums[position] = nums[child]; // 如果较大的孩子节点比父节点大,则孩子节点替换父节点的位置
else break; // 如果父节点已是子节点中最大,直接退出循环
}
nums[position] = temp; // 如果修改了父节点的值,回填相应的子节点
return nums;
}
public int[] heapSort(int[] nums, int size){
int i;
int temp;
// 初始建堆,从最后一个非叶子节点开始遍历
for (i = size/2 - 1; i >= 0; i--)
nums = siftDown(nums, i, size);
for (i = size-1; i >= 0; i--){ // 一共需要遍历size-1次(删除堆顶元素之后反复调整堆)
temp = nums[0]; // 将堆顶元素与子序列中最后一个元素交换
nums[0] = nums[i];
nums[i] = temp;
nums = siftDown(nums, 0, i); // 将nums[0...i]重新调整为大根堆
}
return nums;
}
时间复杂度
堆排序的时间主要由建堆和反复调整两部分时间开销构成。由
n
n
n 个元素建成的堆，其深度为
h
=
⌊
l
o
g
n
⌋
+
1
h=lfloor logn rfloor + 1
h=⌊logn⌋+1，根节点向下调整时能移动的最大层数为
h
−
1
h-1
h−1，元素的最大比较次数为
2
(
h
−
1
)
2(h-1)
2(h−1) 次；第
i
i
i 层最多有
2
i
−
1
2^{i-1}
2i−1 个节点，对于，对于第
i
i
i 层的节点，向下调整堆进行性的元素比较的次数最多为
2
(
h
−
i
)
2(h-i)
2(h−i)，因此，建堆的元素比较的次数最多为
T
(
n
)
T(n)
T(n)，它满足以下表达式
T ( n ) T(n) T(n) = ∑ i = 1 i = h − 1 2 n − i ∗ 2 ( h − i ) sum_{i=1}^{i=h-1} 2^{n-i} * 2(h-i) i=1∑i=h−12n−i∗2(h−i) <= ∑ i = 1 i = h − 1 2 n ∗ 2 ( h − i ) sum_{i=1}^{i=h-1} 2^n * 2(h-i) i=1∑i=h−12n∗2(h−i) <= 4 n 4n 4n
建堆的时间复杂度为 O ( n ) O(n) O(n)。反复调整堆的操作体现在 heapSort 的第2个for循环中，共计调用siftDown()函数 n − 1 n-1 n−1 次，该循环的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。因此，堆排序的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度
在堆排序的过程中，只需要一个元素大小的辅助空间用于存放堆顶的最大元素，因此空间复杂度为
O
(
1
)
O(1)
O(1)
