在 C++ 標準模板庫(STL) 中排序
-
在 C++ 中使用
sort()函式對陣列或 STL 容器進行排序 - 在 C++ 中按降序對陣列進行排序
-
使用
partial_sort()函式對陣列或向量的一部分進行排序 -
使用 C++ 中的
sort()函式的使用者定義或自定義排序 -
在 C++ 中使用
is_sorted()方法 - 排序演算法的時間複雜度
在本教程中，我們將學習一個廣泛使用的 C++ 函式，稱為 sort()。我們還將檢視與排序相關的其他功能。
為了在 C++ 中對資料進行排序，我們編寫演算法並將其應用於資料，或者我們可以使用 C++ STL 中的內建函式 sort()。sort() 函式在 algorithm 標頭檔案中定義。
此函式使用 IntroSort 演算法，這是一種混合排序演算法，它使用三種排序演算法，快速排序、堆排序和插入排序，以最大限度地減少執行時間。
此函式對給定範圍的元素進行排序。
語法：
sort(start iterator, end iterator, compare_function)
預設情況下，這將按升序對開始迭代器和結束迭代器定義的範圍內的元素進行排序（這是預設的 compare_function）。
在 C++ 中使用 sort() 函式對陣列或 STL 容器進行排序
排序是對資料執行的基本操作之一。我們以遞增、遞減或使用者定義（自定義排序）的方式排列資料。
我們可以在 C++ 中使用 sort() 函式對陣列或 STL 容器（如 vector、set、map 等）進行排序。
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};
// array size
int n = sizeof(arr) / sizeof(arr[0]);
vector<int> v{35, 67, 11, -9, 7, -22}; // vector
cout << "The array after sorting is : \n";
sort(arr, arr + n);
sort(v.begin(), v.end()); // sorting vector
for (int i = 0; i < n; ++i) cout << arr[i] << " ";
cout << endl;
cout << "The vector after sorting is : \n";
for (int i = 0; i < v.size(); ++i) cout << v[i] << " ";
}
輸出：
The array after sorting is :
0 1 2 3 4 5 6 7 8 9
The vector after sorting is :
-22 -9 7 11 35 67
預設情況下，專案按升序排列。
在 C++ 中按降序對陣列進行排序
要按降序對 C++ STL 中存在的陣列或容器進行排序，我們必須在 sort() 函式中傳遞名為 greater<type>() 的第三個引數。此函式執行比較，以便最後的元素按降序排序。
Type 指的是我們正在使用的陣列或容器的型別，int、float 或 string 型別。
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};
// array size
int n = sizeof(arr) / sizeof(arr[0]);
vector<int> v{35, 67, 11, -9, 7, -22}; // vector
cout << "The array after sorting is : \n";
sort(arr, arr + n, greater<int>());
sort(v.begin(), v.end(), greater<int>()); // sorting vector
for (int i = 0; i < n; ++i) cout << arr[i] << " ";
cout << endl;
cout << "The vector after sorting is : \n";
for (int i = 0; i < v.size(); ++i) cout << v[i] << " ";
}
輸出：
The array after sorting is :
9 8 7 6 5 4 3 2 1 0
The vector after sorting is :
67 35 11 7 -9 -22
使用 partial_sort() 函式對陣列或向量的一部分進行排序
我們可以使用 partial_sort() 對陣列的某些部分進行排序。這種方法只不過是原始排序方法的變體。
語法：
partial_sort(first, middle, last)
它重新排列範圍（first，last）中的元素，以便中間之前的元素按升序排序，中間之後的元素沒有任何特定順序。
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
vector<int> vr{35, 67, 11, -9, 7, -22}; // vector
cout << "The vector after partial sorting is : \n";
partial_sort(vr.begin(), vr.begin() + 2, vr.end());
for (int i = 0; i < vr.size(); ++i) cout << vr[i] << " ";
}
輸出：
The vector after partial sorting is :
-22 -9 67 35 11 7
我們可以觀察到只有前兩個元素被排序，剩下的只是以某種隨機順序出現。
使用 C++ 中的 sort() 函式的使用者定義或自定義排序
只要我們想對資料進行升序或降序排序，都可以使用這個函式，但有時我們希望資料以使用者自定義的方式排序。
在這裡，我們必須編寫自定義排序函式，我們將作為第三個引數傳遞給 sort() 函式。
#include <algorithm>
#include <iostream>
using namespace std;
bool myfunction(string x, string y) { return x.size() < y.size(); }
int main() {
string str[] = {"a", "abc", "ba", "abcd"};
int n = 4;
sort(str, str + n); // normal sort function
cout << "Array after sorting : \n";
for (int i = 0; i < n; ++i) cout << str[i] << " ";
cout << endl;
sort(str, str + n, myfunction);
cout << "Array after user defined sorting : \n";
for (int i = 0; i < n; ++i) cout << str[i] << " ";
}
輸出：
Array after sorting :
a abc abcd ba
Array after user defined sorting :
a ba abc abcd
第一種排序方法預設按字典升序對字串陣列進行排序。第二種排序方法根據字串的長度對字串進行排序，即我們在名為 myfunction 的自定義比較函式中提到的條件。
在 C++ 中使用 is_sorted() 方法
如果我們想檢查給定範圍的資料是否排序，我們可以使用這種方法。
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
vector<int> v{35, 67, 11, -9, 7, -22}; // vector
cout << is_sorted(v.begin(), v.end());
}
輸出：
0
由於向量沒有排序，我們得到的輸出為 0，意思是假。
排序演算法的時間複雜度
sort() 的時間複雜度為 O(NlogN)，其中 N 是應用 sort() 函式的元素的數量。
