[C++] algorithm

Posted on Tue, Aug 24, 2021 C++
2021-10-13更新

sort

sort 可以針對array或vector進行排列

基本用法

sort(iter first,iter last,cmp)

array

int a[10]={3,1,4,1,5,9,2,6,7,8,0};
sort(a,a+9);
//or
sort(a,a+sizeof(a)/sizeof(int));//可以自動計算陣列長度
sort(a,a+8);//也可以指定範圍做排序

vector

vector<int> v = {3,1,4,1,5,9,2,6,7,8,0};
sort(v.begin(),v.end())

使用sort(v.rbegin(),v.rend())可以在排序後反轉,和使用sort後再reverse類似。

可以自訂比較函式進行排列

int a[10]={3,1,4,1,5,9,2,6,7,8,0};
bool cmp1(int a,int b){
		return a>b;//i+1>i就交換 -> 升序
}
sort(a,a+10,cmp1)
int a[10]={3,1,4,1,5,9,2,6,7,8,0};
bool cmp2(int a,int b){
		return a<b;//i+1<i就交換 -> 降序
}
sort(a,a+10,cmp2)

參考

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

本篇介紹 C++ 的 std::sort 排序用法,C++ 最常用到的就是對 vector sort 排序,或對傳統陣列 array sort 排序,以上兩種都會在本篇介紹,C++ 的 sort 預設排序方式是升序,也可以用降序或自定義的排序方式,詳見下列內容,接下來就開始介紹 C++ 的 sort 排序吧。 市面上的排序法有很多,有泡沫排序法、快速排序法、合併排序法,這篇將介紹不用自己寫(刻),用 C++ STL 標準函式庫提供的 sort 來排序,首先來簡單介紹 C++ sort 最基本的用法, 需要引入的標頭檔: 這樣就可以完成排序囉~接下來就認真介紹 C++ sort 多種範例與寫法,以及補充說明,分別如下, 範例1. 排序 sort array 傳統陣列,並使用預設排序方式(升序) 範例2. 排序 sort array 傳統陣列(降序) 範例3. 排序 sort vector,並使用預設排序方式(升序) 範例4. 排序 sort vector,並使用函式排序(降序) 範例5.

lower_bound&upper_bound

lower_bound可以在 binary search 時用到

vector <int> v = {4,2,6,8,5,7,3,9};
sort(v.begin(),v.end())

要使用[[vector]]等資料結構,不能使用陣列,在執行前也要先排好。

auto low = lower_bound(v.begin(), v.end(), val);
auto up = upper_bound(v.begin(), v.end(), val);

使用[[auto]]自動判斷型態,val指定大於等於其的最小值。

reverse

可以將array或vector順序反轉,和[[sort]]使用方式非常相似。

array

int a[10]={3,1,4,1,5,9,2,6,7,8,0};
sort(a,a+9);
//or
reverse(a,a+sizeof(a)/sizeof(int));

vector

vector<int> v = {3,1,4,1,5,9,2,6,7,8,0};
reverse(v.begin(),v.end())