【STL源码剖析】list::sort真的好用吗？Centos7-Linux环境g++Release下vector数组排序和list排序效率测试【超详细的注释和解释】

 

---

说在前面的话

在使用C++的标准模板库的一些容器时，我们难免会遇到给序列排序的问题。

在学习list的时候，我们可能会了解到，algorithm::sort其实不是万能的。

当我们要给list排序的时候，我们可能会用到list::sort。

今天，我们就来探讨一下，给一堆数据排序，用vector+algorithm::sort效率较高，还是用list+list::sort效率更高！

前言

那么这里博主先安利一下一些干货满满的专栏啦！

手撕数据结构https://blog.csdn.net/yu_cblog/category_11490888.html?spm=1001.2014.3001.5482这里包含了博主很多的数据结构学习上的总结，每一篇都是超级用心编写的，有兴趣的伙伴们都支持一下吧！
算法专栏https://blog.csdn.net/yu_cblog/category_11464817.html这里是STL源码剖析专栏，这个专栏将会持续更新STL各种容器的模拟实现。

STL源码剖析https://blog.csdn.net/yu_cblog/category_11983210.html?spm=1001.2014.3001.5482

---

两种排序的底层排序算法效率分析

algorithm::sort使用的是快速排序及其优化

list::sort使用的是归并排序（因为链式存储结构归并是常数级别的空间复杂度）

学过排序算法我们可以了解到，归并排序和快速排序的平均时间复杂度都是O(nlogn)，它们两者是属于同一级别的排序算法。

现在让我们来分别测试一下VS和g++环境下的效率对比。

测试代码

//现在有n(很大)个数据需要排序，哪一种好？
//1.vector+algorithm::sort
//2.list+list::sort
//写个程序来看一下,用release跑
//vector快
//当大量数据需要访问的时候，vector的随机访问性的优势就能体现出来了
void TestOP() {
	srand(time(0));
	const int N = 10000000;
	vectorv;
	v.reserve(N);
	listlt1;
	listlt2;
	for (int i = 0; i < N; i++) {
		auto e = rand();
		v.push_back(e);
		lt2.push_back(e);
	}
	//拷贝到vector排序，排完之后再拷贝回来
	int begin1 = clock();
	sort(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	lt2.sort();
	int end2 = clock();

	cout << "vectorSort" << " " << end1 - begin1 << endl;
	cout << "listSort" << " " << end2 - begin2 << endl;
}
int main() {
	TestOP();
	return 0;
}

测试结果

VS环境下：

g++环境下结果：

结果：

很明显，用vector的效率是更高的。

这是为什么呢？

我们都知道，vector底层是顺序表，也就是数组。数组是具有随机访问性的，这是链表所不具备的。因此，当我们有大量的数据需要访问和 *** 作时，vector的优势就体现出来了！

其实，list::sort基本上时很少用的。

尾声

如果你们感觉这篇文章对你们有帮助的话，不要忘记一键三连噢！你们的支持是我最大的动力！

更多文章请访问我的主页

@背包https://blog.csdn.net/Yu_Cblog?spm=1000.2115.3001.5343