vector实现的原地堆排序的效率问题
来源:4-6 优化的堆排序(Heap Sort)
Ian_Song
2020-01-28
老师您好,在学习堆排序的时候,我根据您的讲解,用类实现了一个最大堆,其中用一个数组成员变量data来存储数据,但在实现原地堆排序函数的时候,我按自己习惯用了vector,结果发现这样实现的堆排序比之前用类实现的heapSort1和heapSort2在各个数量级的数据上都慢上了差不多一倍,这是vector内部的机制造成的吗?以下是我的实现:
template<typename T>
void _shiftDown(std::vector<T>& vec, int k, int count) {
while (2 * k + 1 < count){
int j = 2 * k + 1;
if (2 * k + 2 < count && vec[2 * k + 2] > vec[2 * k + 1]) {
j = 2 * k + 2;
}
if (vec[k] > vec[j]) break;
std::swap(vec[k], vec[j]);
k = j;
}
}
template<typename T>
void heapSort(std::vector<T>& vec) {
//Heapify
int count = vec.size();
for (int i = (count - 1) / 2; i >= 0; i--) {
_shiftDown(vec, i, count);
}
//Sort
for (int i = count - 1; i >= 1; i--) {
std::swap(vec[0], vec[i]);
count--;
_shiftDown(vec, 0, count);
}
写回答
1回答
-
是的,C++ 的 STL 内部封装的 vector,很多时候性能效率不如直接使用静态数组。因为内部有很多没必要的检查判断。
在一些极端情况下,我遇到过 OJ 上的题目,使用静态数组 AC,使用 vector 直接 TLE。
继续加油!:)
112020-01-28
相似问题