一、简介
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。我们在编程过程中会经常接触到排序，比如游戏中的排行榜等。C++标准库中提供了各种不同的排序算法，这篇博客将逐一介绍。还有在什么场景下，具体该使用哪一个排序算法效率更高。
二、算法
1. sort
原型:
template
void sort(iterator begin, iterator end)
template
void sort(iterator begin, inerator end, compare comp)
事例:
下面是2个参数版本的全排序函数sort的使用事例
#include
#include
#include ? ? ? //各种迭代器
#include ? ? //各种算法
using namespace std;
int randint()
{
? ? ? ? static int sr = time(NULL);
? ? ? ? srand(++sr);
? ? ? ? return rand() % 100;
}
int main()
{
? ? ? ? vector vecInt;
? ? ? ? generate_n(back_inserter(vecInt), 5, randint);? //生成5个随机数放入vecInt中
? ? ? ? sort(vecInt.begin(), vecInt.end());
? ? ? ? copy(vecInt.begin(), vecInt.end(), ostream_iterator(cout, "\n"));? ? //输出
? ? ? ? return 0;
}
#程序执行结果
23
24
88
90
99
这个事例介绍3个参数版本的全排序函数sort，将学生按照分数进行递增、递减排序，下面的事例代码都是基于这个学生分数来写的。
#include
#include
#include
#include
#include ? ? //ostream_iterator
#include ? //not2
using 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
{
? ? ? ? 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 stuArray(stu, stu + sizeof(stu) / sizeof(student));
? ? ? ? sort(stuArray.begin(), stuArray.end(), comp());? ? ? //递增排序
? ? ? ? copy(stuArray.begin(), stuArray.end(), ostream_iterator(cout, ""));
? ? ? ? cout << "=======" << endl;
? ? ? ? sort(stuArray.begin(), stuArray.end(), not2(comp())); //递减排序
? ? ? ? copy(stuArray.begin(), stuArray.end(), ostream_iterator(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
void sort(iterator begin, iterator end)
template
void sort(iterator begin, inerator end, compare comp)
sort和stable_sort都是全排序函数，但是sort是非稳定排序算法，而stable_sort是稳定排序算法。在稳定排序算法中，如果区间中的两个元素有等价的值，那么在排序之后，它们的相对位置不会发生变化。比如学生A和学生B都是60分，并且学生A在学生B的前面，那么在递增排序后学生A还会在学生B的前面。而非稳定的排序并不保证这一点。
3. partition
原型:
template
iterator partition(iterator begin, iterator end, predicate pred)
功能:
对[begin,end]区间内满足pred判定条件的所有元素移到前部，然后返回一个迭代器，指向第一个不满足条件元素。
事例:
现在有一个需求，就是从所有学生中筛选中分数大于60分的人。这个时候全排序就不是那么好使了，当然你可以进行递增全排序后，然后找到60的元素所在的位置，输出它之后的元素，这是个很笨的方法。如果换个需求筛选出分数为偶数的人呢，全排序就没辙了，这时候就用到partition了。
#include
#include
#include
#include
#include ? ? //ostream_iterator
#include ? //not2
using 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
{
? ? ? ? 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("f