1

【c++標準函式庫(STL)筆記】利用<algorithm>裡面的sort()函數幫助我們排序

C++中的sort有兩種形式：

`template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last);`

`template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);`

sort()函數的前兩個參數指的是要排序對象的範圍，

範例- 對array 遞增或遞減排序

``````#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};
int n = sizeof(arr)/sizeof(arr[0]);

sort(arr, arr+n);

cout << "陣列遞增排序後的結果為: \n";
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";

sort(arr, arr+n, greater<int>());

cout << "\n陣列遞減排序後的結果為: \n";
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
return 0;
}
``````

`陣列遞增排序後的結果為:`
`0 1 2 3 4 5 6 7 8 9`
`陣列遞減排序後的結果為:`
`9 8 7 6 5 4 3 2 1 0`

範例- 對vector 遞增或遞減排序

``````#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

cout << "陣列遞增排序後的結果為: \n";
for (int i = 0; i < arr.size(); ++i)
cout << arr[i] << " ";

sort(arr.begin(), arr.end(), greater<int>());

cout << "\n陣列遞減排序後的結果為: \n";
for (int i = 0; i < arr.size(); ++i)
cout << arr[i] << " ";
return 0;
}
``````

`陣列遞增排序後的結果為:`
`0 1 2 3 4 5 6 7 8 9`
`陣列遞減排序後的結果為:`
`9 8 7 6 5 4 3 2 1 0`

範例- 對vector的一部分排序

``````#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
vector<int> arr = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};
sort(arr.begin()+2, arr.begin()+5); //指定幫arr[2]~arr[4]範圍排序

cout << "陣列遞增排序後的結果為: \n";
for (int i = 0; i < arr.size(); ++i)
cout << arr[i] << " ";
return 0;
}
``````

`陣列遞增排序後的結果為:`
`1 5 6 8 9 7 3 4 2 0`

範例- 對自定義的物件做自定義規則排序

``````#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 自定義物件: 有start time 和 end time
struct Interval
{
int start, end;
};

// 定義若Interval i1的起始時間較小，則Interval i1 < Interval i2
bool compareInterval(Interval &i1, Interval &i2)
{
return (i1.start < i2.start);
}

int main()
{
vector<Interval> arr =  { {6,8}, {1,9}, {2,4}, {4,7} };
sort(arr.begin(), arr.end(), compareInterval);

cout << "對自定義物件Interval排序後的結果為: \n";
for (int i = 0; i < arr.size(); ++i)
cout << "[" << arr[i].start << "," << arr[i].end << "] ";
return 0;
}
``````

`對自定義物件Interval排序後的結果為:`
`[1,9] [2,4] [4,7] [6,8]`

`[] (參數1, ..., 參數n) {return something};`
(接近python語法中的`lambda 參數1, ..., 參數n: return something`的感覺)

``````#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 自定義物件: 有start time 和 end time
struct Interval
{
int start, end;
};

int main()
{
vector<Interval> arr =  { {6,8}, {1,9}, {2,4}, {4,7} };
sort(arr.begin(), arr.end(), [](Interval &i1, Interval &i2){return (i1.start < i2.start);});

cout << "對自定義物件Interval排序後的結果為: \n";
for (int i = 0; i < arr.size(); ++i)
cout << "[" << arr[i].start << "," << arr[i].end << "] ";
return 0;
}
``````

例題- 973. K Closest Points to Origin

``````Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
``````

寫法一、lambda函數(380 ms)

c++程式碼:

``````class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
sort(points.begin(), points.end(), [](auto &p1, auto &p2){
return (p1[0]*p1[0]+p1[1]*p1[1])< (p2[0]*p2[0]+p2[1]*p2[1]);});
return vector<vector<int>>(points.begin(), points.begin()+K);
}
};
``````

寫法二、寫普通函數傳進sort()(380 ms)

``````class Solution {
static bool compare(vector<int> &p1, vector<int> &p2)
{
return (p1[0]*p1[0]+p1[1]*p1[1]) < (p2[0]*p2[0]+p2[1]*p2[1]);
}
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
sort(points.begin(), points.end(), compare);
return {points.begin(), points.begin()+K};
}
};
``````