C++ std::sort 排序用法與範例完整介紹

本篇介紹 C++ 的 std::sort 排序用法,C++ 最常用到的就是對 vector sort 排序,或對傳統陣列 array sort 排序,以上兩種都會在本篇介紹,C++ 的 sort 預設排序方式是升序,也可以用降序或自定義的排序方式,詳見下列內容,接下來就開始介紹 C++ 的 sort 排序吧。

市面上的排序法有很多,有泡沫排序法、快速排序法、合併排序法,這篇將介紹不用自己寫(刻),用 C++ STL 標準函式庫提供的 sort 來排序,
首先來簡單介紹 C++ sort 最基本的用法,
需要引入的標頭檔<algorithm>

1
2
3
vector<int> v;
// ...
std::sort(v.begin(), v.end());

這樣就可以完成排序囉~
接下來就認真介紹 C++ sort 多種範例與寫法,以及補充說明,分別如下,
範例1. 排序 sort array 傳統陣列,並使用預設排序方式(升序)
範例2. 排序 sort array 傳統陣列(降序)
範例3. 排序 sort vector,並使用預設排序方式(升序)
範例4. 排序 sort vector,並使用函式排序(降序)
範例5. 排序 sort vector,並使用 lambda function 匿名函式排序(升序)
範例6. 排序 sort vector,並使用函式物件排序(降序)
範例7. 排序字串 sort string (升序)
範例8. 排序自定義結構 sort struct (降序)
補充. 排序陣列的某部份
補充. 自動計算陣列總長度
補充. C++ 的 std::sort 跟 C 的 qsort 誰比較快?
補充. 誰也使用了 std::sort ?

範例1. 排序 sort array 傳統陣列,並使用預設排序方式(升序)

如何用 C++ sort array 對 c-style 傳統陣列排序的範例如下,
宣告一個 arr 傳統陣列並且初始化好數值,
再使用 std::sort 針對 array 進行排序,
預設提供的一個比較函數(升冪/升序/由小到大),
當你需要按照某種特定方式進行排序時,例如降冪,你需要給 sort 指定比較函數,後面例子會提到。

std-sort1.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// g++ std-sort1.cpp -o a.out
#include <iostream>
#include <algorithm>

int main() {
int arr[] = {4, 5, 8, 3, 7, 1, 2, 6, 10, 9};
std::sort(arr, arr+10);
std::cout << "sort array by default (increasing):" << std::endl;
for (int i = 0; i < 10; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;

return 0;
}

輸出如下:

1
2
sort array by default (increasing):
1 2 3 4 5 6 7 8 9 10

你也可以用 std::begin()std::end() 取得 c-style 陣列的頭跟尾,像這樣寫

1
std::sort(std::begin(arr), std::end(arr));

範例2. 排序 sort array 傳統陣列(降序)

從上例可了解 c++ sort 升冪的使用,那降冪(降序/由大到小)要如何使用呢?
分為兩種方法,一種是自訂排序方式,在 std::sort 第三個參數傳入一個可以降冪的 function object 函式物件(又稱 functor 仿函式),這個方式稍後的範例會提到,
另一種方法是使用<functional>提供的比較函式物件讓我們方便使用,在 std::sort 第三個參數傳入比較樣板函式物件即可,
<functional>提供的比較樣板函式物件分別有
less<Type>:小於,i+1小於i的就交換swap(升序)
less_equal<Type>:小於等於,i+1小於等於i的就交換swap(升序)
greater<Type>:大於,i+1大於i的就交換swap(降序)
greater_equal<Type>:大於等於,i+1大於等於i的就交換swap(降序)
equal_to<Type>:等於,i+1等於i的就交換swap
not_equal_to<Type>:不等於,i+1不等於i的就交換swap
以上這幾種,而實際上用法如下:

升序:std::sort(begin, end, less<Type>());
降序:std::sort(begin, end, greater<Type>());

接著來看看實際範例吧!
在這個例子中,我們就是在 std::sort 第三個參數傳入 std::greater<int>() 來達成降冪(降序/由大到小)的排序,

std-sort2.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// g++ std-sort2.cpp -o a.out
#include <iostream>
#include <algorithm>
#include <functional>

int main() {
int arr[] = {4, 5, 8, 3, 7, 1, 2, 6, 10, 9};
std::sort(arr, arr+10, std::greater<int>());
std::cout << "sort array (decreasing):" << std::endl;
for (int i = 0; i < 10; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;

return 0;
}

輸出如下:

1
2
sort array (decreasing):
10 9 8 7 6 5 4 3 2 1

範例3. 排序 sort vector,並使用預設排序方式(升序)

上述例子都是介紹傳統陣列,接著開始介紹對 std::vector 容器排序的用法,將 vector 帶入 std::sort 函式排序,
你可以使用 std::sort(v.begin(), v.begin()+10); 的方式,
也可以使用 std::sort(v.begin(), v.end()); 的方式隨君喜好,
最後的結果都是升序的(由小到大),如下範例所示,
關於怎麼在 std::sort 函式的第三個參數帶入自訂的函式將會下個範例會介紹,以及簡單地理解第三個參數怎麼在 std::sort 裡運作,

std-sort3.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// g++ std-sort3.cpp -o a.out -std=c++11
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
std::vector<int> v = {5, 4, 1, 7, 3, 8, 9, 10, 6, 2};
std::sort(v.begin(), v.begin()+10);
// or
//std::sort(v.begin(), v.end());
std::cout << "sort vecotr by default (increasing):" << std::endl;
for (int i = 0; i < v.size(); i++) {
std::cout << v[i] << " ";
}
std::cout << std::endl;

return 0;
}

輸出如下:

1
2
sort vecotr by default (increasing):
1 2 3 4 5 6 7 8 9 10

範例4. 排序 sort vector,並使用函式排序(降序)

上述提到 std::sort 可以使用自訂排序方式來排序, 這個例子就來示範一下,
如下列範例所示,使用 mycompare function 作為比較函式,我們可以在 mycompare 裡自訂我們想要的排序規則,
例子中的 return a > b 為降序的示範,這其實跟上述介紹的 greater<Type> 是等價一樣的效果,

簡單理解第三個參數怎麼在 std::sort 內部裡運作
先不討論 std::sort 內部是用哪種排序演算法,
我們可以先簡單地解讀成 sort 內部有兩層迴圈,不斷地針對 vector 的 index 0 頭掃到 index n 尾,直到排序結束為止,
而迴圈每次都會將 i+1 與 i 帶入 mycompare 的參數,i+1 就是 a, i 就是 b,
如此一來 a > b 就會將 i+1 與 i 交換 swap,這樣就會一直將越大的數值排越前面,
若不懂排序原理的可以參考最簡單的排序法:泡沫排序法,

std-sort4.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// g++ std-sort4.cpp -o a.out -std=c++11
#include <iostream>
#include <algorithm>
#include <vector>

bool mycompare(int a, int b) {
return a > b; // 降序排列
}

int main() {
int arr[] = {5, 4, 1, 7, 3, 8, 9, 10, 6, 2};
std::vector<int> v(arr, arr+10);
std::sort(v.begin(), v.end(), mycompare);
std::cout << "sort vecotr by function (decreasing):" << std::endl;
for (int i : v) {
std::cout << i << " ";
}
std::cout << std::endl;

return 0;
}

輸出如下:

1
2
sort vecotr by function (decreasing):
10 9 8 7 6 5 4 3 2 1

另外降序還有第三個方式,就是使用 vector 反向迭代的方式,從 vector 尾部逆向迭代到頭部,這算是善用 vector 的小技巧,例如下面這樣寫,

1
std::sort(v.rbegin(), v.rend());

範例5. 排序 sort vector,並使用 lambda function 匿名函式排序(升序)

這個範例介紹匿名函式 lambda function 來搭配 sort 使用,
如下列範例所示,在sort第三個參數中直接帶入一個匿名函式 lambda function 作為參數,
其匿名函式內容為回傳 a < b,這樣就達成的升序的排列結果。

std-sort5.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// g++ std-sort5.cpp -o a.out -std=c++11
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
std::vector<int> v = {5, 4, 1, 7, 3, 8, 9, 10, 6, 2};
std::sort(v.begin(), v.end(), [](int a, int b){
return a < b; // 升序排列
});
std::cout << "sort vecotr by lambda function (increasing):" << std::endl;
for (int i : v) {
std::cout << i << " ";
}
std::cout << std::endl;

return 0;
}

輸出如下:

1
2
sort vecotr by lambda function (increasing):
1 2 3 4 5 6 7 8 9 10

範例6. 排序 sort vector,並使用函式物件排序(降序)

sort 帶入 function object 函式物件來排序,function object 函式物件又稱 functor 仿函式,
其實就是重載了 operator() 運算子的一個類別,如下列範例中的 myclass,
其目的在於讓它可以像函式一樣呼叫使用,例如:myclass(5, 3); 會回傳 5,
那我們就來看看怎麼用函式物件結合 sort 來使用,
如下範例所示,直接在 std::sort 的第三個參數帶入 myclass 函式物件,

std-sort6.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// g++ std-sort6.cpp -o a.out -std=c++11
#include <iostream>
#include <algorithm>
#include <vector>

struct myclass {
bool operator() (int a, int b) { return a > b; } // 降序排列
} myobject;

int main() {
std::vector<int> v = {5, 4, 1, 7, 3, 8, 9, 10, 6, 2};
std::sort(v.begin(), v.end(), myobject);
std::cout << "sort vecotr by object (decreasing):" << std::endl;
for (int i : v) {
std::cout << i << " ";
}
std::cout << std::endl;

return 0;
}

輸出如下:

1
2
sort vecotr by object (decreasing):
10 9 8 7 6 5 4 3 2 1

範例7. 排序字串 sort string (升序)

介紹一下在 C++ 中怎麼對字串 std::string 排序 sort,很簡單,就直接看範例吧!
將 std::string 傳入 std::sort 函式,在第三參數帶入 std::less<char>() 來達成升冪(升序/由小到大)的排序(按ASCII碼字母順序),

std-sort7.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// g++ std-sort7.cpp -o a.out -std=c++11
#include <iostream>
#include <algorithm>
#include <string>

int main() {
std::string s = "eacdb";
std::sort(s.begin(), s.end(), std::less<char>());
std::cout << "sort string (increasing):" << std::endl;
for (char c : s) {
std::cout << c << " ";
}
std::cout << std::endl;

return 0;
}

輸出如下:

1
2
sort string (increasing):
a b c d e

範例8. 排序自定義結構 sort struct (降序)

這邊介紹 C++ 如何排序自定義結構 sort struct ,下面範例中有個 student 的結構,內部欄位有姓名與分數,
我們最常對學生的分數按高低分來排名,一開始先初始化學生的姓名與分數後,接著讓 mycompare 回傳降序的方式,
而這個 mycompare 是接受我們自定義的 student 結構,並且最後回傳 student.score 的比較結果,
降序的方式上述已經介紹過,忘了請往回看,
之後就可以按照分數由高到低排序完成。

std-sort8.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// g++ std-sort8.cpp -o a.out -std=c++11
#include <iostream>
#include <algorithm>
#include <string>

struct student {
std::string name;
int score;
};

bool mycompare(student s1, student s2){
return s1.score > s2.score;
}

int main() {
student st[4];
st[0].name = "bob";
st[0].score = 70;
st[1].name = "cindy";
st[1].score = 66;
st[2].name = "alice";
st[2].score = 77;
st[3].name = "alice";
st[3].score = 76;

std::sort(st, st+4, mycompare);
std::cout << "sort struct (decreasing):" << std::endl;
for (student s : st) {
std::cout << s.name << " " << s.score << std::endl;
}
std::cout << std::endl;

return 0;
}

這邊故意設計兩個學生都叫 alice 但分數不一樣的情形,看看是不是也能排序,結果也是可以的,
輸出如下:

1
2
3
4
5
sort struct (decreasing):
alice 77
alice 76
bob 70
cindy 66

好了!以上就是 C++ std::sort 的介紹與用法範例,sort 的排序法有很多種,
知名的排序法有泡沫排序法、快速排序法、合併排序法,
排序不但是實務上常用的技能到且考試很容易考得考題,可見排序的重要性,所以一定要好好地學起來。

補充. 排序陣列的某部份

如果你只想排序前5筆數值,其他數值不排序,可以這樣寫,

1
2
int arr[] = {4, 5, 8, 3, 7, 1, 2, 6, 10, 9};
std::sort(arr, arr+5);

輸出如下:

1
3 4 5 7 8 1 2 6 10 9

如果是用 vector 的話,就變成這樣寫,

1
2
std::vector<int> arr = {4, 5, 8, 3, 7, 1, 2, 6, 10, 9};
std::sort(arr.begin(), arr.begin()+5);

輸出結果也是一樣的。

如果你想排序第3筆到第5筆數值,其他數值不動,可以這樣寫,
(排序從std::sort第一個參數開始,直到(小於)第二個參數之前)

1
2
int arr[] = {4, 5, 8, 3, 7, 1, 2, 6, 10, 9};
std::sort(arr+2, arr+5);

輸出如下:

1
4 5 3 7 8 1 2 6 10 9

如果是用 vector 的話,就變成這樣寫,

1
2
std::vector<int> arr = {4, 5, 8, 3, 7, 1, 2, 6, 10, 9};
std::sort(arr.begin()+2, arr.begin()+5);

輸出結果也是一樣的。
其他依此類推。

補充. 自動計算陣列總長度

每次排序整個 c-style 陣列需要先計算好陣列的總長度,如果你想寫得聰明一點,避免自己手動去算有幾個或算錯的話,
可以這樣寫,用 sizeof 來取得整個陣列的總 byte 數除以 int 的 byte 數,就是整個陣列的總長度了,

1
2
3
int arr[] = {4, 5, 8, 3, 7, 1, 2, 6, 10, 9};
int len = sizeof(arr) / sizeof(int);
std::sort(arr, arr + len);

補充. C++ 的 std::sort 跟 C 的 qsort 誰比較快?

C++ STL 的 std::sort (<algorithm>) 與 C 的 qsort (<cstdlib>)這兩個排序哪個比較快?
這問題顯然大家已經知道了,那就是 C++ STL 的 std::sort 比 qsort 更快,
以前已經知道有個快速排序法已經很快了,沒想到 std::sort 還更快,
不論你想手刻或是使用 qsort 一定都不會比 std::sort 還要快,對這部份有興趣的也可自行作實驗挑戰看看
如果沒把握還是乖乖用大神寫好的 std::sort 吧!

補充. 誰也使用了 std::sort ?

誰也使用了 std::sort ? 來看看別人是怎麼使用的吧!
OpenCV 內部使用 std::sort 的範例,OpenCV VideoBackend 有很多種,
所以這邊是根據 VideoBackend 的 Priority 來進行排序,以便之後的使用
https://github.com/opencv/opencv/blob/master/modules/videoio/src/videoio_registry.cpp

1
2
3
4
5
6
bool sortByPriority(const VideoBackendInfo &lhs, const VideoBackendInfo &rhs)
{
return lhs.priority > rhs.priority;
}

std::sort(enabledBackends.begin(), enabledBackends.end(), sortByPriority);

其他參考
sort - C++ Reference
http://www.cplusplus.com/reference/algorithm/sort/
詳細解說 STL 排序(Sort) - C++ Programmer’s Cookbook - C++博客
http://www.cppblog.com/mzty/archive/2005/12/15/1770.aspx

其它相關文章推薦
C/C++ 新手入門教學懶人包
std::thread 用法與範例
std::deque 用法與範例
std::find 用法與範例
std::mutex 用法與範例
std::unordered_map 用法與範例
std::random_shuffle 產生不重複的隨機亂數
std::shared_ptr 用法與範例
std::async 用法與範例