2016 August 12

堆排序

堆排序是另一种时间复杂度为O(nlogn)的排序算法，它的实现依赖于二叉堆，优点是就地排序，无需额外空间，最坏时间复杂度也是O(nlogn)，缺点是不稳定。

理解了二叉堆，堆排序可谓水到渠成。仍以整型数组按从小到大排序为例，由于要求从小到大排，得用大根堆，步骤如下：

  1. 建立大根堆
  2. 从堆中弹出最大元素，将它与下标最大的乱序元素交换
  3. 因弹出堆顶元素对堆做调整
  4. 反复执行2~3步骤，直到堆空为止
void SiftDown(int *a, int size, int idx) {
    int i, j;
    for (i = idx; (j = 2 * i + 1) < size; i = j) {
        if (j + 1 < size && a[j+1] > a[j])
            j += 1;
        if (a[j] <= a[i])
            break;
        swap(&a[i], &a[j]);
    }
}
void Heapify(int *a, int size) {
    int i;
    for (i = (size - 1) / 2; i >= 0; i--)
        SiftDown(a, size, i);
}
void HeapSort(int *a, int size) {
    int i;
    Heapify(a, size);
    for (i = size - 1; i > 0; i--) {
        swap(&a[0], &a[i]);
        SiftDown(a, i, 0);
    }
}

由于这里数组下标是从0开始的，需注意：

Table of Contents