c - 单独使用递归构建最小堆

Question

这是尝试仅通过函数调用来进行堆排序构建堆。问题是它需要太长的时间才能完成，比同一项目中编写的更简单的冒泡排序要长，接近 100 秒，而冒泡排序需要 42 秒，按降序排列有 100000 个条目。合并排序和快速排序从未超过一秒。如果编译器未能进行尾部调用优化，它会在 100000 处崩溃，这一点没关系。

它曾经崩溃过，实现上的一些细节是为了使尾部调用发生。它已经在降序、升序和随机分布的数据上进行了测试。还进行了一些更改，以弥补其速度缓慢的问题，以及导致其外观困惑的原因。

int heap_sort_step(int v[], int len, int i){
    int nextl = 2 * i + 1, nextr = nextl + 1;
    char bfl = (nextl<len)|((nextr<len)<<1);

    switch(bfl)
    {
        case 3:
        case 2:
            while(v[i] > heap_sort_step(v, len, nextr))
                swap(v + i, v + nextr);
        case 1:
            while(v[i] > heap_sort_step(v, len, nextl))
                swap(v + i, v + nextl);
        default:
            return v[i];
    }

}

void heap_sort(int v[], int len){
    return (len > 1)?
                (heap_sort_step(v, len, 0),
                 heap_sort(v + 1, len - 1)):
            NULL;
}

heap_sort(int v[], int len) 接受一个数组及其大小，并使用 heap_sort_step() 为数组中的每个成员构建最小堆，并对其进行排序。这里需要尾调用。

heap_sort_step(int v[], int len, int i) 接受一个数组、它的大小和用于构建堆的索引，其方程如 nextl 和 nextr、2i+1 和 2i+2 所示，从 i 开始= 0。 'bfl' 是一个优化技巧(对使用 ifs 的微小改进)，用于通过查看前面是否有更多项目来决定转到哪个分支或仅返回当前值。 switch 使用fallthrough，是构建堆的位置，3 和2 表示右侧有内容(0b11 和0b10)，1 表示左侧有内容(0b01)，默认行为是返回当前编号。以前的写法是这样的:

int heap_sort_step(int v[], int len, int i){
    int nextl = (((i + 1) * 2) - 1), nextr = nextl + 1;
    if(nextl < len)
        while(v[i] > heap_sort_step(v, len, nextl))
            swap(v + i, v + nextl);

    if(nextr < len)
        while(v[i] > heap_sort_step(v, len, nextr))
            swap(v + i, v + nextr);

    return v[i];
}

对于递归步骤，它将当前数字与下一个函数调用的返回值进行比较，如果更大，则交换，如果小于，则级联返回到根。

此时我非常确定这只是一个糟糕的实现，并且想知道这是否是由于更改或其他原因造成的复杂性问题。它可以使用相同的概念与归并排序和快速排序竞争吗？应该是 O n(log(n))，对吗？

Answer 1

抛开递归对性能的影响以及如何依靠尾部调用优化使 heap_sort() 函数成为非递归的问题不谈，您的实现并没有看起来像堆排序。堆排序可以这样描述:

1. 将要排序的元素排列到堆中(天真的，O(n log n)；深思熟虑，O(n))
2. 只要堆中至少有两个元素，(O(n) 次迭代)
   1. 将头元素与最后一个元素交换。 (O(1))
   2. 将(逻辑)堆大小减少 1。(O(1))
   3. 恢复堆状态。 (如果做得正确的话，O(log n))

当然，无论您是使用最大堆按升序排序还是使用最小堆按降序排序，这都适用。

正如您在评论中澄清的那样，您的方法是将数组排列到最小堆中以获得最小元素，然后对数组的 n - 1 个元素尾部重复。 这不是堆排序——它是选择排序的变体。如果实现得好，其成本为 O(n²)，因为每个堆构建步骤必须至少访问 n/2 个非叶节点，因此成本为 O(n)。