- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
这是尝试仅通过函数调用来进行堆排序构建堆。问题是它需要太长的时间才能完成,比同一项目中编写的更简单的冒泡排序要长,接近 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)),对吗?
最佳答案
抛开递归对性能的影响以及如何依靠尾部调用优化使 heap_sort()
函数成为非递归的问题不谈,您的实现并没有看起来像堆排序。堆排序可以这样描述:
当然,无论您是使用最大堆按升序排序还是使用最小堆按降序排序,这都适用。
正如您在评论中澄清的那样,您的方法是将数组排列到最小堆中以获得最小元素,然后对数组的 n - 1 个元素尾部重复。 这不是堆排序——它是选择排序的变体。如果实现得好,其成本为 O(n2),因为每个堆构建步骤必须至少访问 n/2 个非叶节点,因此成本为 O(n)。
关于c - 单独使用递归构建最小堆,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56926089/
我是一名优秀的程序员,十分优秀!