在 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()
函式的元素的數量。