STl中的排序算法詳細解析

2020-01-26 15:49:23

字體：大中小

來源：轉載

供稿：網友

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時，你可以直接使用這些函數模板。但如果你時自己定義的類型或者你需要按照其他方式排序，你可以有兩種方法來達到效果：一種是自己寫比較函數。另一種是重載類型的'<'操作賦。

3. 全排序：

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

用于全排序的函數有：

1.void sort(RandomAccessIterator first, RandomAccessIterator last);

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

3.void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

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

4. 局部排序：

partial_sort采用的堆排序（heapsort），它在任何情況下的復雜度都是n*log(n)。

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

其函數原型為：

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

4.2 void partial_sort(RandomAccessIterator first,RandomAccessIterator middle,RandomAccessIterator last, StrictWeakOrdering comp);

4.3 RandomAccessIterator partial_sort_copy(InputIterator first, InputIteratorlast,RandomAccessIteratorresult_first,RandomAccessIterator result_last);

4.4 RandomAccessIterator partial_sort_copy(InputIterator first, InputIteratorlast,RandomAccessIteratorresult_first,RandomAccessIterator result_last, Compare comp);

例如：班上有1000個學生，我想知道分數最低的5名是哪些人。

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

5. nth_element 指定元素排序

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

5.2 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就是把一個區間中的元素按照某個條件分成兩類，并沒有排序。

其函數原型為：

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