DIV CSS 佈局教程網

您现在的位置: DIV+CSS佈局教程網 >> 網頁腳本 >  >> XML學習教程 >> XML詳解
深入解說 STL 排序(Sort)系列函數的用法與選擇
編輯:XML詳解     

一切複雜的排序操作,都能透過 STL 輕鬆實現!

前言:為什麼你必須掌握 STL


對程式設計師而言,資料結構是必修的一門課。從查找、排序到鏈表、二叉樹,幾乎所有算法與原理都得理解,理解不了也要硬背下來。所幸這些理論多已成熟、算法也大致定型,你不需要再花心思去推翻其原理或驗證正確性。可是,當你真正用程式語言投入工作時會發現:面對不同需求,你得一次又一次用程式碼重新實作這些成熟算法,還會一再掉進因疏忽而產生的 bug 裡。這時你會渴望有個工具,早已幫你實作好這些功能,讓你隨心所欲地取用,又不影響效能——這就是 STL,標準模板庫!

西方有句諺語:不要重複發明輪子!

STL 幾乎封裝了資料結構中的所有算法,從鏈表到佇列、從向量到堆疊、從 hash 到二叉樹、從搜尋到排序、從新增到刪除……可以說,一旦你理解了 STL,就不再拘泥於算法本身,而能站在巨人的肩膀上思考更高階的應用。

排序是最廣泛的算法之一,本文將詳細說明 STL 中各種排序函數的用法與差異。

一、STL 提供的 Sort 系列算法


C++ 之所以廣受喜愛,是因為它兼具物件導向概念與 C 語言的高效能。STL 排序算法同樣講求效率,因此針對不同需求提供了不同的函數,而各函數背後實作的算法也不盡相同。

1.1 所有 sort 算法概覽

所有 sort 算法的參數都需要傳入一個範圍 [begin, end),且使用的迭代器必須是隨機訪問迭代器(RandomAccessIterator),也就是能以 it+n 方式隨機訪問的迭代器(partition 與 stable_partition 除外)。若你需要自訂比較方式,可以把自定義的仿函數(functor)作為參數傳入,每種算法都支持傳入比較函數。以下是所有 STL sort 系列函數:

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

其中 nth_element 最不易理解,實際上它是用來「找出第幾個」。例如:找出含 7 個元素的陣列中排在正中央那個數,此時你既不關心前面、也不在意後面,只想知道排在第四位的元素值是多少。

1.2 sort 中的比較函數

當你想以特定方式排序時,需要給 sort 指定比較函數,否則程式會自動提供一個預設的比較函數。

vector < int > vect; //...
sort(vect.begin(), vect.end()); //此時相當於呼叫 sort(vect.begin(), vect.end(), less<int>() );

上述例子中,系統為 sort 提供了 less 仿函數。STL 還提供了其他仿函數:

名稱 —— 功能描述
equal_to —— 相等
not_equal_to —— 不相等
less —— 小於
greater —— 大於
less_equal —— 小於等於
greater_equal —— 大於等於

要注意的是,這些函數並非都適用於你的 sort 場景,如何取捨取決於你的應用。此外,不能直接寫仿函數的名字,而要寫其重載的 () 函數:

less<int>()
greater<int>()

當容器中元素是標準型別(int、float、char)或 string 時,你可以直接使用這些函數模板。但如果你自訂型別,或想以其他方式排序,有兩種做法:一是自己撰寫比較函數,二是重載型別的 '<' 運算子。

#include <iOStream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
class myclass {
public:
    myclass(int a, int b):first(a), second(b){}
    int first;
    int second;
    bool Operator < (const myclass &m)const {
        return first < m.first;
    }
};
bool less_second(const myclass & m1, const myclass & m2) {
    return m1.second < m2.second;
}
int main() {
    vector< myclass > vect;
    for(int i = 0 ; i < 10 ; i ++){
        myclass my(10-i, i*3);
        vect.push_back(my);
    }
    for(int i = 0 ; i < vect.size(); i ++) cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
    sort(vect.begin(), vect.end());
    cout<<"after sorted by first:"<<endl;
    for(int i = 0 ; i < vect.size(); i ++) cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
    cout<<"after sorted by second:"<<endl;
    sort(vect.begin(), vect.end(), less_second);
    for(int i = 0 ; i < vect.size(); i ++) cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
    return 0 ;
}

輸出結果如下:

(10,0) (9,3) (8,6) (7,9) (6,12) (5,15) (4,18) (3,21) (2,24) (1,27)
after sorted by first:
(1,27) (2,24) (3,21) (4,18) (5,15) (6,12) (7,9) (8,6) (9,3) (10,0)
after sorted by second:
(10,0) (9,3) (8,6) (7,9) (6,12) (5,15) (4,18) (3,21) (2,24) (1,27)

1.3 sort 的穩定性

你可能會好奇,為什麼有 sort 和 stable_sort、partition 和 stable_partition 之分。差別在於:帶 stable 的函數能保證「相等元素」在排序後的相對次序維持不變。或許你會問,既然相等,還分誰先誰後有意義嗎?這裡要釐清一個觀念:這裡的「相等」,指的是你提供的比較函數判定兩者相等,並不一定是完全一模一樣的元素。

例如,如果你寫了一個比較函數:

bool less_len(const string &str1, const string &str2) {
    return str1.length() < str2.length();
}

此時 "apple" 與 "winter" 就是「相等」的(長度相同)。若 "apple" 原本排在 "winter" 前面,用帶 stable 的函數排序後,它們的次序一定不變;若改用不帶 stable 的函數,排序後 "winter" 有可能跑到 "apple" 前面。

1.4 全排序

全排序即把給定範圍內所有元素依大小關係完整排列。用於全排序的函數原型如下:

template <class RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering> void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);
template <class RandomAccessIterator> void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering> void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);

在第 1、3 種形式中,sort 與 stable_sort 都未指定比較函數,系統預設使用 operator< 對區間 [first,last) 內所有元素排序,因此若你的型別已重載 Operator<,就能省事了。第 2、4 種形式則可自訂比較函數,應用更為靈活。來看實際應用——班上有 10 個學生,我想知道他們的成績排名:

#include <iOStream>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
using namespace std;
class student{
public:
    student(const string &a, int b):name(a), score(b){}
    string name;
    int score;
    bool Operator < (const student &m)const {
        return score< m.score;
    }
};
int main() {
    vector< student> vect;
    student st1("Tom", 74); vect.push_back(st1);
    st1.name="Jimy"; st1.score=56; vect.push_back(st1);
    st1.name="Mary"; st1.score=92; vect.push_back(st1);
    st1.name="Jessy"; st1.score=85; vect.push_back(st1);
    st1.name="Jone"; st1.score=56; vect.push_back(st1);
    st1.name="Bush"; st1.score=52; vect.push_back(st1);
    st1.name="Winter"; st1.score=77; vect.push_back(st1);
    st1.name="Andyer"; st1.score=63; vect.push_back(st1);
    st1.name="Lily"; st1.score=76; vect.push_back(st1);
    st1.name="Maryia"; st1.score=89; vect.push_back(st1);
    cout<<"------before sort..."<<endl;
    for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
    stable_sort(vect.begin(), vect.end(),less<student>());
    cout <<"-----after sort ...."<<endl;
    for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
    return 0 ;
}

輸出如下:

------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Bush: 52
Jimy: 56
Jone: 56
Andyer: 63
Tom: 74
Lily: 76
Winter: 77
Jessy: 85
Maryia: 89
Mary: 92

sort 採用成熟的「快速排序算法」(目前大部分 STL 版本已非單純的快速排序,而是結合內插排序),可保證很好的平均效能,複雜度為 n*log(n)。由於單純快速排序理論上有最差情況(複雜度為 n*n),但目前多數 STL 版本都已做了優化,因此可放心使用。stable_sort 則採用「歸並排序」,在分配足夠記憶體時複雜度為 n*log(n),否則為 n*log(n)*log(n),其優點是保持相等元素排序前後的相對位置不變。

1.5 局部排序

局部排序其實是為了減少不必要的操作而提供的排序方式,函數原型如下:

template <class RandomAccessIterator> void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering> void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, StrictWeakOrdering comp);
template <class InputIterator, class RandomAccessIterator> RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last);
template <class InputIterator, class RandomAccessIterator, class StrictWeakOrdering> RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);

理解了 sort 與 stable_sort 後,partial_sort 就不難懂。班上有 10 個學生,我想知道分數最低的 5 名是哪些人。若沒有 partial_sort,你得先用 sort 把所有人排好序再取前 5 個;現在你只需對分數最低 5 名排序,把前面的程式改一行即可:

stable_sort(vect.begin(), vect.end(),less<student>()); 替換為:
partial_sort(vect.begin(), vect.begin()+5, vect.end(),less<student>());

輸出結果為:

------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Bush: 52
Jimy: 56
Jone: 56
Andyer: 63
Tom: 74
Mary: 92
Jessy: 85
Winter: 77
Lily: 76
Maryia: 89

當資料量小時可能看不出優勢,但若是 100 萬個學生要找分數最少的 5 個人,差異就很明顯了。partial_sort 採用堆排序(heapsort),任何情況下複雜度都是 n*log(n)。若你想用 partial_sort 實作全排序,只要讓 middle=last 即可。partial_sort_copy 則是 copy 與 partial_sort 的組合,被排序(複製)的數量取 [first, last) 與 [result_first, result_last) 中較小的那個區間。

1.6 nth_element 指定元素排序

nth_element 是個容易看懂卻不易解釋的排序函數,用例子說明會更清楚:班上有 10 個學生,我想知道分數排倒數第 4 名的學生。要滿足這個需求,可以用 sort 排好序後取第 4 位(因為由小到大排),更聰明的做法是用 partial_sort 只排前 4 位。但其實這仍有浪費,因為前兩位根本不必排序,這時就该用 nth_element:

template <class RandomAccessIterator> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, StrictWeakOrdering comp);

針對上述需求,只需把 1.4 的程式改一行:

stable_sort(vect.begin(), vect.end(),less<student>()); 替換為:
nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());

運行結果為:

------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Jone: 56
Bush: 52
Jimy: 56
Andyer: 63
Jessy: 85
Mary: 92
Winter: 77
Tom: 74
Lily: 76
Maryia: 89

第四名是誰?Andyer。為什麼是 begin()+3 而不是 +4?因為 begin() 是第一個,begin()+1 是第二個,依此類推,begin()+3 自然就是第四個了。

1.7 partition 和 stable_partition

這兩個函數嚴格說來並非用於排序,稱之為「分類」算法會更貼切。partition 把一個區間中的元素依某個條件分成兩類,函數原型如下:

template <class ForwardIterator, class Predicate> ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred)
template <class ForwardIterator, class Predicate> ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);

看看應用:班上 10 個學生,要計算所有沒有及格(低於 60 分)的學生,只需替換 1.4 的程式:

stable_sort(vect.begin(), vect.end(),less<student>()); 替換為:
student exam("pass", 60);
stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));

輸出結果為:

------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Jimy: 56
Jone: 56
Bush: 52
Tom: 74
Mary: 92
Jessy: 85
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89

看見了嗎?Jimy、Jone、Bush 都沒有及格。而且因為用的是 stable_partition,元素之間的相對次序沒有改變。

二、Sort 與容器


STL 標準容器主要有 vector、list、deque、string、set、multiset、map、multimap,其中 set、multiset、map、multimap 都是以樹結構儲存元素,因此它們中的元素一直是有序的。

這些容器的迭代器類型並不是隨機型迭代器,因此上述那些排序函數對它們是不可用的。上述 sort 函數對下列容器可用:

  • vector
  • string
  • deque

如果你自訂的容器也支持隨機型迭代器,那麼使用排序算法完全沒問題。對於 list 容器,它自帶一個 sort 成員函數 list::sort(),與算法函數中的 sort 差不多,但 list::sort 是以指標方式排序,也就是所有資料的移動與比較都以指標方式實現,因此排序後的迭代器仍保持有效(vector 中 sort 後的迭代器會失效)。

三、選擇合適的排序函數


為什麼要選擇合適的排序函數?或許你並不關心效率,或者你的資料量很小,覺得隨便用哪個函數都無關緊要。其實不然,即使不講效率,選對排序函數也能讓你的程式碼更易讀、更有擴充性,逐漸養成好習慣。

如果你以前用過 C 語言的 qsort,想知道它與上述函數的比較,那我告訴你:qsort 和 sort 一樣,採用的都是快速排序。從效率上看,以下 sort 系列算法由快到慢(耗時由小到大)為:

  1. partition
  2. stable_partition
  3. nth_element
  4. partial_sort
  5. sort
  6. stable_sort

關於「如何選擇排序函數」,可以參考以下建議:

  • 若需對 vector、string、deque 或 array 容器進行全排序,可選擇 sort 或 stable_sort;
  • 若只需取得 vector、string、deque 或 array 中的 top n 元素,partial_sort 是首選;
  • 若你需要找到第 n 個位置的元素,或需要 top n 但不關心其內部順序,nth_element 最理想;
  • 若你需要把滿足或不滿足某條件的元素分開,最好使用 partition 或 stable_partition;
  • 若使用 list 容器,可直接用 partition 和 stable_partition,並用 list::sort 代替 sort 與 stable_sort;若想得到 partial_sort 或 nth_element 的效果,則必須間接實現。

總之記住一句話:如果你想節約時間,就不要走彎路,也不要走多餘的路!

四、小結


討論技術就像個無底洞,容易從一點引申出無數技術點,因此需要從全局角度觀察問題,就像觀察 STL 中的 sort 算法一樣。其實 STL 裡還有 make_heap、sort_heap 等排序算法,本文未觸及。本文以實例方式說明了 STL 排序算法的特性,並總結了在實際情況下該如何選擇合適的算法。

五、參考文檔

條款31:如何選擇排序函數
The Standard Librarian: Sorting in the Standard Library
Effective STL 中文版
Standard Template Library Programmer's Guide

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved