所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。我们在编程过程中会经常接触到排序，比如游戏中的排行榜等。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> //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<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> //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<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)
功能: