原地堆性能较好的一个因素是不是没有封装成一个类啊
来源：4-6 优化的堆排序（Heap Sort）
Suspendz
2020-08-05
原地堆性能较好的一个主要的因素是不是没有封装成一个类，而是直接通过函数传参修改原始数组中相应位置的数据啊？因为我之前自己写了一版原地堆，是封装成了一个类，里面成员变量指针指向传入的数组(也算是没有新开辟空间吧)，还有一个count记录当前需要处理的是data[0,count]，写了一个跟课程里逻辑基本上一样的交换首尾元素->count减一->data[0,count]索引为0的位置元素进行shiftdown操作。
然后写了个sort(T arr[],int n)方法，实例化了这个类然后执行该对象的排序方法
最后测试的时候发现使用这个封装好的类进行排序的速度比之前那个版本通过extract方法还要稍慢一点(100w个元素慢了0.05秒的样子)。
后来跟着课程改成了直接通过函数修改arr，发现速度快了非常多(100w个元素原地堆比之前那个extract快了0.1秒)，但是核心思路都是一样的。
所以就感觉是不是问题出在了对象实例化的上面？
1回答
-
我不确定你的具体实现方式，因为这个课程中，所有的排序算法都没有封装成一个类。但是把算法封装成一个类确实会降低性能。
但是，原地堆排序的 heapify 过程，从复杂度的角度，确实比直接使用堆性能高。因为一个是 O(n) 的，一个是 O(nlogn) 的。但是，O(nlogn) 和 O(n) 的算法之间，性能差距很小，也是正常的，因为 O(logn) 实在太快了，不容易看出来。不过我印象里，这一点我在课程的代码中能测试出来。如果使用 100 万的数据觉得看的不清晰的话，可以试验一下 1000 万的数据。
继续加油！：）
012020-08-19
相似问题