C++排序算法 algorithm

學習網站：http://www.stlchina.org/twiki/bin/view.pl/Main/STLTechArticles

                   http://www.stlchina.org/twiki/bin/view.pl/Main/STLSortAlgorithms

排序(sort)：所有sort算法介紹:使用的疊代器(iterator)都需是随機疊代器(RadomAccessIterator)

1.      所有STL sort算法函數的名字清單:

函數名	功能描述
sort	對給定區間所有元素進行排序
stable_sort	對給定區間所有元素進行穩定排序
partial_sort	對給定區間所有元素部分排序
partial_sort_copy	對給定區間複制并排序
nth_element	找出給定區間的某個位置對應的元素
is_sorted	判斷一個區間是否已經排好序
partition	使得符合某個條件的元素放在前面
stable_partition	相對穩定的使得符合某個條件的元素放在前面

2.      比較函數：當你需要按照某種特定方式進行排序時，你需要給sort指定比較函數，否則程式會自動提供給你一個比較函數。

vector < int > vect;

//...

sort(vect.begin(), vect.end());

//此時相當于調用

sort(vect.begin(), vect.end(), less<int>() );

sort 中的其他比較函數

equal_to	相等
not_equal_to	不相等
less	小于
greater	大于
less_equal	小于等于
greater_equal	大于等于

上述例子中系統自己為sort提供了less仿函數。在STL中還提供了其他仿函數，以下是仿函數清單:

不能直接寫入仿函數的名字，而是要寫其重載的()函數： less<int>();

當你的容器中元素時一些标準類型（int float char)或者string時，你可以直接使用這些函數模闆。但如果你

時自己定義的類型或者你需要按照其他方式排序，你可以有兩種方法來達到效果：一種是自己寫比較函數。另一種是重載類型的'<'操作賦。如：

bool less_second(const myclass & m1, const myclass & m2) {

        return m1.second < m2.second;

}

3.      全排序：全排序即把所給定範圍所有的元素按照大小關系順序排列。sort采用的是成熟的"快速排序算法"(目前大部分STL版本已經不是采用簡單的快速排序，而是結合内插排序算法)。複雜度為n*log(n).stable_sort采用的是"歸并排序"，分派足夠記憶體是，其算法複雜度為n*log(n), 否則其複雜度為n*log(n)*log(n)，其優點是會保持相等元素之間的相對位置在排序前後保持一緻。

用于全排序的函數有：

void sort(RandomAccessIterator first, RandomAccessIterator last);

void sort(RandomAccessIterator first, RandomAccessIterator last,StrictWeakOrdering comp);

void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);

4.      局部排序：partial_sort采用的堆排序（heapsort），它在任何情況下的複雜度都是n*log(n).

局部排序其實是為了減少不必要的操作而提供的排序方式。

其函數原型為：

1)      void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last);

2)      void partial_sort(RandomAccessIterator first,RandomAccessIterator middle,

         RandomAccessIterator last, StrictWeakOrdering comp);

3)      RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,

         RandomAccessIterator result_first,RandomAccessIterator result_last);

4)      RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,

         RandomAccessIterator result_first,RandomAccessIterator result_last, Compare comp);

用法使用情況：班上有1000個學生，我想知道分數最低的5名是哪些人。

partial_sort(vect.begin(), vect.begin()+5, vect.end(),less<student>());

5.      nth_element 指定元素排序

         void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

         void nth_element(RandomAccessIterator first, RandomAccessIterator nth,RandomAccessIterator last,

                   StrictWeakOrdering comp);

使用情況：班上有1000個學生，我想知道分數排在倒數第4名的學生。

nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());

6.          partition 和stable_partition :partition就是把一個區間中的元素按照某個條件分成兩類，并沒有排序。

         其函數原型為：

         ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred)

         ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);

         用法如：班上10個學生，計算所有沒有及格（低于60分）的學生：

         student exam("pass", 60);

         stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));

7.      效率由高到低（耗時由小變大）：

         partion

         stable_partition

         nth_element

         partial_sort

         sort

         stable_sort

8.      Effective STL對如何選擇排序函數總結的很好：

         1)      若需對vector, string, deque, 或 array容器進行全排序，你可選擇sort或stable_sort；

若隻需對vector, string, deque, 或 array容器中取得top n的元素，部分排序partial_sort是首選.

若對于vector, string, deque, 或array容器，你需要找到第n個位置的元素或者你需要得到top n且不關系top

         2)      n中的内部順序，nth_element是最理想的；

         3)      若你需要從标準序列容器或者array中把滿足某個條件或者不滿足某個條件的元素分開，你最好使用partition或stable_partition；

         4)      若使用的list容器，你可以直接使用partition和stable_partition算法，你可以使用list::sort代替sort和stable_sort排序。若你需要得到partial_sort或nth_element的排序效果，你必須間接使用。