一、簡介
所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。我們在編程過程中會經常接觸到排序，比如游戲中的排行榜等。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)
功能:
迭代器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> //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));
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