vector实现的原地堆排序的效率问题

来源:4-6 优化的堆排序(Heap Sort)

Ian_Song

2020-01-28

老师您好,在学习堆排序的时候,我根据您的讲解,用类实现了一个最大堆,其中用一个数组成员变量data来存储数据,但在实现原地堆排序函数的时候,我按自己习惯用了vector,结果发现这样实现的堆排序比之前用类实现的heapSort1heapSort2在各个数量级的数据上都慢上了差不多一倍,这是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回答

liuyubobobo

2020-01-28

是的,C++ 的 STL 内部封装的 vector,很多时候性能效率不如直接使用静态数组。因为内部有很多没必要的检查判断。


在一些极端情况下,我遇到过 OJ 上的题目,使用静态数组 AC,使用 vector 直接 TLE。


继续加油!:)

1
1
Ian_Song
感谢老师如此及时的解答!
2020-01-28
共1条回复

算法与数据结构(C++版) 面试/评级的算法复习技能包

课程专为:短时间内应对面试、升职测评等艰巨任务打造

11237 学习 · 1617 问题

查看课程