C++标准库中各种排序归纳

一、简介

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。我们在编程过程中会经常接触到排序，比如游戏中的排行榜等。C++标准库中提供了各种不同的排序算法，这篇博客将逐一介绍。还有在什么场景下，具体该使用哪一个排序算法效率更高。

二、算法

1. sort

原型: 

template<typename iterator>
void sort(iterator begin, iterator end)template <typename iterator, typename compare>
void sort(iterator begin, inerator end, compare comp)

事例: 

下面是2个参数版本的全排序函数sort的使用事例

#include <iostream>
#include <vector>
#include <iterator>      //各种迭代器
#include <algorithm>    //各种算法using namespace std;int randint()
{static int sr = time(NULL);srand(++sr);return rand() % 100;
}int main()
{vector<int> vecInt;generate_n(back_inserter(vecInt), 5, randint);  //生成5个随机数放入vecInt中sort(vecInt.begin(), vecInt.end());copy(vecInt.begin(), vecInt.end(), ostream_iterator<int>(cout, "\n"));    //输出return 0;
}

#程序执行结果
[root@oracle ~]# ./a.out 
23
24
88
90
99

这个事例介绍3个参数版本的全排序函数sort，将学生按照分数进行递增、递减排序，下面的事例代码都是基于这个学生分数来写的。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>     //ostream_iterator
#include <functional>   //not2using namespace std;struct student
{string name;			//名字unsigned int score;		//分数student(const string &n, unsigned int s) :name(n),score(s){}  friend ostream & operator<<(ostream &os, const student &rhs){   return os << rhs.score << " : " << rhs.name << endl;}   
};//按学生的分数进行排序
struct comp : public binary_function<student, student, bool>
{bool operator()(const student &lhs, const student &rhs) const{return lhs.score < rhs.score;}
};int main()
{student stu[] = { student("aa", 100),student("bb", 95),student("cc", 50),student("dd", 40),student("ee", 52),student("ff", 60),student("gg", 86),student("hh", 60),student("ii", 83),student("jj", 91),};  vector<student> stuArray(stu, stu + sizeof(stu) / sizeof(student));sort(stuArray.begin(), stuArray.end(), comp());		//递增排序copy(stuArray.begin(), stuArray.end(), ostream_iterator<student>(cout, ""));cout << "=======" << endl;sort(stuArray.begin(), stuArray.end(), not2(comp()));	//递减排序copy(stuArray.begin(), stuArray.end(), ostream_iterator<student>(cout, ""));return 0;
}

#程序执行结果
[root@oracle ~]# ./a.out 
40 : dd
50 : cc
52 : ee
60 : ff
60 : hh
83 : ii
86 : gg
91 : jj
95 : bb
100 : aa
=======
100 : aa
95 : bb
91 : jj
86 : gg
83 : ii
60 : hh
60 : ff
52 : ee
50 : cc
40 : dd

2. stable_sort

原型: 

template<typename iterator>
void sort(iterator begin, iterator end)template <typename iterator, typename compare>
void sort(iterator begin, inerator end, compare comp)

sort和stable_sort都是全排序函数，但是sort是非稳定排序算法，而stable_sort是稳定排序算法。在稳定排序算法中，如果区间中的两个元素有等价的值，那么在排序之后，它们的相对位置不会发生变化。比如学生A和学生B都是60分，并且学生A在学生B的前面，那么在递增排序后学生A还会在学生B的前面。而非稳定的排序并不保证这一点。

3. partition

原型: 

template<typename iterator, typename predicate>
iterator partition(iterator begin, iterator end, predicate pred)

功能:

对[begin,end]区间内满足pred判定条件的所有元素移到前部，然后返回一个迭代器，指向第一个不满足条件元素。

事例:

现在有一个需求，就是从所有学生中筛选中分数大于60分的人。这个时候全排序就不是那么好使了，当然你可以进行递增全排序后，然后找到60的元素所在的位置，输出它之后的元素，这是个很笨的方法。如果换个需求筛选出分数为偶数的人呢，全排序就没辙了，这时候就用到partition了。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>     //ostream_iterator
#include <functional>   //not2using namespace std;struct student
{string name;unsigned int score;student(const string &n, unsigned int s) :name(n),score(s){}  friend ostream & operator<<(ostream &os, const student &rhs){   return os << rhs.score << " : " << rhs.name << endl;}   
};struct comp : public unary_function<student, bool>
{bool operator()(const student &stu) const{return stu.score > 60;}
};int main()
{student stu[] = {student("aa", 100),student("bb", 95),student("cc", 50),student("dd", 40),student("ee", 52),student("ff", 60),student("gg", 86),student("hh", 60),student("ii", 83),student("jj", 91),};vector<student> stuArray(stu, stu + sizeof(stu) / sizeof(student));vector<student>::iterator it = partition(stuArray.begin(), stuArray.end(), comp());copy(stuArray.begin(), it, ostream_iterator<student>(cout, ""));	//输出分数大于60分的人cout << "=======" << endl;copy(it, stuArray.end(), ostream_iterator<student>(cout, ""));	//输出分数小于等于60分的人return 0;
}

#程序执行结果
[root@oracle ~]# ./a.out 
100 : aa
95 : bb
91 : jj
83 : ii
86 : gg
=======
60 : ff
52 : ee
60 : hh
40 : dd
50 : cc

4. stable_partition

原型: 

template<typename iterator, typename predicate>
iterator stable_partition(iterator begin, iterator end, predicate pred)

从名字可以看出来，它是partition的稳定排序版本。

5. nth_element

原型: 

template<typename iterator>
void nth_element(iterator begin, iterator nth, iterator end)template<typename iterator, typename compare>
void nth_element(iterator begin, iterator nth, iterator end, compare comp)

功能:

迭代器nth用来指向一个全排序的情况下第n个元素的位置，然后根据这个值将[begin, end]区间内的元素分割成2部分，一部分都在元素n的全面，一部分在元素n的后面，但它并不关心分割后元素的排序情况。

事例:

nth_element的功能和partition有点类似，但又不完全相同。partition可以筛选出所有分数大于60分的人，现在需求变成需要筛选出分数最高的前5个人，这时就轮到nth_element出场了。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>     //ostream_iterator
#include <functional>   //not2using namespace std;struct student
{string name;unsigned int score;student(const string &n, unsigned int s) :name(n),score(s){}  friend ostream & operator<<(ostream &os, const student &rhs){   return os << rhs.score << " : " << rhs.name << endl;}   
};struct comp : public binary_function<student, student, bool>
{bool operator()(const student &lhs, const student &rhs) const{return lhs.score > rhs.score;}
};int main()
{student stu[] = {student("aa", 100),student("bb", 95),student("cc", 50),student("dd", 40),student("ee", 52),student("ff", 60),student("gg", 86),student("hh", 60),student("ii", 83),student("jj", 91),};vector<student> stuArray(stu, stu + sizeof(stu) / sizeof(student));nth_element(stuArray.begin(), stuArray.begin() + 5, stuArray.end(), comp());copy(stuArray.begin(), stuArray.begin() + 5, ostream_iterator<student>(cout, ""));return 0;
}

[root@oracle ~]# ./a.out 
100 : aa
95 : bb
91 : jj
83 : ii
86 : gg

6. partial_sort

原型:

template<typename iterator>
void partial_sort(iterator begin, iterator middle, iterator end)template<typename iterator, typename compare>
void partial_sort(iterator begin, iterator middle, iterator end, compare comp)

事例:

partial_sort和nth_element的用法和功能基本相同。不同的是nth_element并不关心符合条件的元素具体的排序位置，只是把他们移到了容器的前面(上面的事例输出也很容易看出来)。而partial_sort则关心具体位置，将nth_element事例中的nth_element函数替换成partial_sort后，输出就变了。

#程序执行结果
[root@oracle ~]# ./a.out 
100 : aa
95 : bb
91 : jj
86 : gg
83 : ii

三、总结

1. sort、stable_sort、partial_sort和nth_element算法都要求随机访问迭代器，所以这些算法只能被用于vector、string、deque和数组。

2. 如果需要对vector、string、deque或者数组中的元素执行一次完全排序，那么可以使用sort或者stable_sort。

3. 如果有一个vector、string、deque或者数组，并且只需要对等价性最前面的n个元素进行排序，那么可以使用partial_sort。

4. 如果有一个vector、string、deque或者数组，并且需要找到第n个位置的元素，或者，需要找到等价性最前面的n个元素但又不必对这n个元素进行排序，那么nth_element正是你所需要的函数。

5. 如果需要将一个标准序列容器中的元素按照是否满足某个特定的条件区分开来，那么，partition和stable_partition可能比较合适。

6. 如果你的数据在一个list中，那么你仍可以直接调用partition和stable_partition算法；可以用list::sort来代替sort和stable_sort算法。但是，如果你需要获得partial_sort或者nth_element算法的效果，那么只能通过一些间接的途径来完成。比如可以将list中的元素复制到一个提供随机访问迭代器的容器中，然后对该容器执行相应的你所期望的排序。

四、性能

总的来说，算法所做的工作越多，它需要的时间也越多。稳定排序算法要比忽略稳定性的算法更耗时。可以依照算法的时间、空间效率对算法进行排序(消耗资源最少的算法排在前面):

1. partition

2. stable_partition

3. nth_element

4. partial_sort

5. sort

6. stable_sort