STL学习-排序算法

1.sort

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

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

2.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());//在全部数据中排出前5
cout<<"排出全部数据的前5:";Show(v2);
v2 = v1;//重新赋值
partial_sort(v2.begin(),v2.begin()+ 5,v2.begin()+ 5);//注意最后一个参数,不是end
cout<<"只对前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;
}

注意：对前五个排序，是把整个容器最小的前五个数据放在前面

3.satble_sort

稳定的排序，采用的是归并排序，O(logn)，但是空间复杂度大

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,10000008);//随机数范围，
//for(inti=0:i<10:++i)//产生10个随机数
//t
//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;
clockt c1=clock();
sort(v1.begin(),v1.end());
clockt_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排序。
在Ubuntu下测试结果如下:(sort最快,stable sort其次,partial sort最慢)