C++STL--排序算法

sort

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

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

对于支持随机访问的迭代器的容器， 都可以利用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);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

partial_sort

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

template<class RandomAccessIterator>
void partial_sort(
RandomAccessIterator first, 
RandomAccessIterator sortEnd,
RandomAccessIterator last
);
1
2
3
4
5
6

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

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>());//降序排序
1
2
3

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

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

注意:

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

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

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

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

测试三种排序的时间差

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

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