C++STL--排序算法

sort

使用快速排序,平均性能好O(nlogn),但最差情况可能很差O(n^2)。不稳定。

sort(v.begin(),v.end());//对v容器进行排序,默认升序
sort(v.begin(),v.end(),greater<int>());//降序排序

对于支持随机访问的迭代器的容器， 都可以利用sort算法直接对其进行排序

下面对deque容器进行排序：

void printDeque(const deque<int>& d)
{//1.迭代器for (auto i = d.begin();i != d.end();i++)cout << *i << " ";cout << endl;//范围for/*for (auto i : d)cout << i << " ";cout << endl;*/
}
int main()
{deque<int>d{ 12,3,5,6,2,4 };	cout << "排序前的deque是： ";printDeque(d);//sort(d.begin(), d.end()); //默认是升序//对于支持随机访问的迭代器的容器， 都可以利用sort算法直接对其进行排序	sort(d.begin(), d.end(), greater<int>()); //降序 需要加一个greater<int>()cout << "排序后的deque是: ";printDeque(d);
}

partial_sort

使用堆排序,平均性能和最差都是O(nlogn),但实际情况比sort慢。不过partial_sort可以对容器的一部分数据排序。不稳定。

template<class RandomAccessIterator>
void partial_sort(
RandomAccessIterator first, 
RandomAccessIterator sortEnd,
RandomAccessIterator last
);

三个参数的含义:
第一个参数:开始迭代器;
第二个参数:堆排序结束迭代器,它距离第一个参数的距离就是最终得到有序数据的个数;
第三个参数:元素范围结束迭代器。
请注意第二个参数,它的含义类似得到前多个有序的数。

partial_sort(v.begin(),v.begin()+5,v.end());//对前5个数据排序
partial_sort(v.begin(),v.end,v.end());//对所有数据排序
partial_sort(v.begin(),v.end,v.end(),greater<int>());//降序排序

这个函数使用较复杂,具体如下:

#include<algorithm>
#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v1{3, 1, 7, 6, 9, 2, 1, 5, 78, 23};vector<int> v2;cout << "排序前:"; Show(v1);v2 = v1;partial_sort(v2.begin(), v2.begin() + 5,v2.end());//在全部数据中排出前5cout << "排出全部数据的前5:"; Show(v2);v2 = v1;//重新赋值partial_sort(v2.begin(), v2.begin() + 5, v2.begin() + 5);//注意最后一个参数,不是endcout << "只对前5个排序后:"; Show(v2);v2 = v1;//重新赋值partial_sort(v2.begin(),v2.end(),v2.end());cout << "全部排序后:"; Show(v2);v2 = v1;//重新赋值partial_sort(v2.begin()+5,v2.end(),v2.end());//前5个数据不排序cout << "前5个数据不排序:"; Show(v2);return 0;
}

注意:

• 对前5个排序,实际是把整个容器最小的5个数据放到最前面。

  对前5个不排序,就真的没有排序前5个。

stable_sort
稳定的排序。采用的是归并排序。O(nlogn),但空间复杂度较大。

stable_sort(v.begin(),v.end());//默认升序
stable_sort(v2.begin(), v2.end(),greater<int>());//降序排序

测试三种排序的时间差

#include<algorithm>
#include <iostream>
#include <vector>
#include<numeric>
#include <random>
#include <ctime>
using namespace std;//输出vector的所有元素
template<typename T>
void Show(const vector<T>& v)
{for (auto x : v)cout << x << " ";cout << endl;
}int main()
{const int n = 10000000;default_random_engine engine;//默认随机引擎 //default_random_engine engine(time(NULL));//加上随机种子uniform_int_distribution<unsigned int> di(0, 10000000);//随机数范围,可以不写默认就是提供的类型范围//for (int i = 0; i < 10; ++i) //产生10个随机数//{//  cout << di(engine) << " ";//}//cout << endl;vector<int> v1,v2,v3;int tmp;for (int i = 0; i < n; i++){tmp = di(engine);//产生一个随机数v1.push_back(tmp);}v2 = v1;v3 = v1;clock_t c1 = clock();sort(v1.begin(), v1.end());clock_t c2 = clock();cout << n << "个数字sort排序,时间为" << c2 - c1 << "毫秒" << endl;c1 = clock();stable_sort(v2.begin(), v2.end());c2 = clock();cout << n << "个数字stable_sort排序,时间为" << c2 - c1 << "毫秒" << endl;c1 = clock();partial_sort(v3.begin(), v3.end(),v3.end());c2 = clock();cout << n << "个数字partial_sort排序,时间为" << c2 - c1 << "毫秒" << endl;//验证排序结果正确/*Show(v1);Show(v2);Show(v3);*/return 0;
}

对一千万的数据量进行排序时间统计,结果和书本介绍差别较大<C++标准库 第2版> 512页。在上面的结果中stable_sort(稳定的排序)反而最快。存疑,同学们可以自行研究一下。按照书上的理论sort使用快速排序应该最快,其次是partial_sort使用堆排序,最慢的是stable_sort排序。