iT邦幫忙

1

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

c++

在標頭檔<algorithm>中,
有個好用的函數sort(),
可以幫助我們對可支援隨機存取的容器作排序(例如: 陣列、vector, ...)

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()函數的前兩個參數指的是要排序對象的範圍,
第三個參數Compare是一個函數,
吃兩個參數,用來自定義我們的排序規則,如果前項比後項小則回傳true。

範例- 對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

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

這邊我們自定一個類別叫Interval,有start time 和 end time,
定義start time比較小的Interval比較小。

這邊提個重要觀念,在自定義比較函數的時候,
應該要call by reference,
函數應宣告為bool compareInterval(Interval &i1, Interval &i2)
而非bool compareInterval(Interval i1, Interval i2)
不然效能上可能會差很多。

#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]

補充:在c++11標準之後,c++也有類似python中匿名函數lambda的寫法,
可以簡便的定義函數,
匿名函數的語法為:
[] (參數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

學會基礎語法後,便可以來嘗試練習leetcode上的這一題了
題目: leetcode- 973. K Closest Points to Origin
題意: 給定一些xy平面上的點,給定數字k,求前k個距離原點最近的點。(距離定義採常見的歐式距離)
範例:

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

想法: 把這些點按照距離大小做排序,再取前k個出來即可
這邊採兩種寫法

寫法一、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};
    }
};

這邊需注意在class內將函數當做參數傳遞,需宣告為static函數(參考: reference to non-static member function must be called)

參考資料

  1. geeksforfeeks- std::sort() in C++ STL
  2. geeksforfeeks- C qsort() vs C++ sort()

尚未有邦友留言

立即登入留言