堆排序（HeapSort）
2019-07-12 本文已影响0人
淌水希恩
与归并排序一样，但不同于插入排序的是，堆排序的时间复杂度是O(nlgn)。而与插入排序相同，但不同于归并排序的是，堆排序同样具有空间原址性：任何时候都只需要常数个额外的元素空间存储临时数据。因此，堆排序是集合了我们目前已经讨论的两种排序算法优点的一种排序算法。
如果你了解堆这种数据结构，你应该知道堆是一种优先队列，两种实现，最大堆和最小堆，由于我们这里排序按升序排，所以就直接以最大堆来说吧。
我们完全可以把堆（以下全都默认为最大堆）看成一棵完全二叉树，但是位于堆顶的元素总是整棵树的最大值，每个子节点的值都比父节点小，由于堆要时刻保持这样的规则特性，所以一旦堆里面的数据发生变化，我们必须对堆重新进行一次构建。
(二叉)堆是一个数组，它可以被看成一个近似的完全二叉树，树的根节点是A[1](伪代码默认下标从1开始)，这样给定一个节点的下标i，我们很容易计算得到它的父节点、左孩子和右孩子的下标：
PARENT(i): return int(i / 2)
LEFT(i): return 2i
RIGHT(i): return 2i + 1
"""
伪代码
"""
MAX-HEAPIFY(A, i) //'维护堆性质，时间复杂度为O(lgn)'
l = LEFT(i)
r = RIGHT(i)
if l <= A.heap_size and A[l] > A[i]
largest = l
else
largest = i
if r <= A.heap_size and A[r] > A[largest]
largest = r
if largest != i
exchange A[i] with A[largest]
MAX-HEAPIFY(A, largest)
BUILD-MAX-HEAP(A) //'建堆，具有线性时间复杂度'
A.heap_size = A.length
for i = int(n / 2) downto 1
MAX-HEAPIFY(A, i)
HEAPSORT(A) //'堆排序算法，时间复杂度为O(nlgn)'
BUILD-MAX-HEAP(A)
for i = A.length downto 2
exchange A[1] with A[i]
A.heap_size = A.heap_size - 1
MAX-HEAPIFY(A, 1)
代码实现：
"""
代码来自微信公众号五分钟学算法
"""
public static void sort(int[] arr) {
int length = arr.length;
//构建堆
buildHeap(arr， length);
for ( int i = length - 1; i > 0; i-- ) {
//将堆顶元素与末位元素调换
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
//数组长度-1 隐藏堆尾元素
length--;
//将堆顶元素下沉 目的是将最大的元素浮到堆顶来
sink(arr， 0， length);
}
}
private static void buildHeap(int[] arr， int length) {
for (int i = length / 2; i >= 0; i--) {
sink(arr， i， length);
}
}
/**
* 下沉调整
* @param arr 数组
* @param index 调整位置
* @param length 数组范围
*/
private static void sink(int[] arr， int index， int length) {
int leftChild = 2 * index + 1;//左子节点下标
int rightChild = 2 * index + 2;//右子节点下标
int present = index;//要调整的节点下标
//下沉左边
if (leftChild < length && arr[leftChild] > arr[present]) {
present = leftChild;
}
//下沉右边
if (rightChild < length && arr[rightChild] > arr[present]) {
present = rightChild;
}
//如果下标不相等 证明调换过了
if (present != index) {
//交换值
int temp = arr[index];
arr[index] = arr[present];
arr[present] = temp;
//继续下沉
sink(arr， present， length);
}
}
