堆排序

堆排序利用了堆的特性进行排序。堆是一种近似完全二叉树的结构,满足以下性质:子节点的键值总是小于(或大于)它的父节点。

堆排序的C实现:

void sink(int *n, int i, int len)
{
    int l = 2*i + 1;
    if (l > len - 1) return;
    int r = l + 1;
    int _max_lr = (r > len - 1) ? l : (*(n+r) > *(n+l) ? r : l);
    if (*(n+_max_lr) < *(n+i)) return;
    swap(n+_max_lr, n+i);
    sink(n, _max_lr, len);
}

void heap(int *n, int len)
{
    int i;
    for (i=(len-1)/2; i>=0; i--) {
        sink(n, i, len);
    }

    for (i=0; i<len; i++) {
        swap(n, n+len-1-i);
        sink(n, 0, len-i-1);
    }
}

堆排序最差情况的时间复杂度为\(n \lg n\) .堆排序需要的额外空间为\(O(1)\) .堆排序是不稳定的.

堆排序与快排的比较

  • 快排总体来说较堆排序更快
  • 快排最差情况下接近\(O(n^2)\)
  • 快排需要更多的额外空间

因此,考虑到堆排序最差情况的复杂度上限和需要额外空间的上限,通常将其应用在对实时性要求较高和安全性较高的嵌入式系统中。

堆排序与归并排序的比较

  • 二者时间复杂度均为\(n \lg n\) .
  • 堆排序在数据缓存较小的计算机上更快,因为堆排序需要更少的额外空间。
  • 堆排序不稳定,归并排序稳定。
  • more
comments powered by Disqus