11.4 內建的 sort 函式

主角登場。sort 住在 <algorithm> 函式庫（用 bits/stdc++.h 的人本來就全包了），用法：

sort(開頭位置, 結尾的下一格位置);

它會把「從開頭位置起、到結尾下一格之前」的所有元素由小到大排好。所以排序存在 a[0] ~ a[n-1] 的 n 個數，就寫：

sort(a, a + n);     // a 是 a[0] 的位置，a + n 是 a[n-1] 的「下一格」

上一節的知識直接兌現：a 是開頭位置、a + n 是往後跳 n 格——恰好是最後一個元素 a[n-1] 的下一格。這種「含頭不含尾」的區間慣例叫左閉右開。

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

int main() {
    int a[6] = {6, 3, 2, 5, 4, 1};
    int n = 6;

    sort(a, a + n);                    // 排序 a[0] ~ a[n-1]

    for (int i = 0; i < n; i++) {
        cout << a[i] << ' ';
    }
    cout << '\n';
    return 0;
}

執行結果：

1 2 3 4 5 6

資料若是用 1-base 存在 a[1] ~ a[n]（上冊 6.3 的存法 A），兩端各往後推一格：

sort(a + 1, a + n + 1);    // 開頭是 a[1] 的位置，結尾下一格是 a[n] 的下一格

¶由大到小：greater()

sort 預設由小到大。要由大到小，傳入第三個參數 greater()：

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

int main() {
    int a[6] = {6, 3, 2, 5, 4, 1};
    int n = 6;

    sort(a, a + n, greater());         // 由大到小

    for (int i = 0; i < n; i++) {
        cout << a[i] << ' ';
    }
    cout << '\n';
    return 0;
}

執行結果：

6 5 4 3 2 1

同一顆 greater() 排什麼型態都對——int、double、string 都是它，不必跟著換寫法。

greater 的正式住址是 <functional>，不過 g++ 的 <algorithm> 一直都拿得到——寫 sort 本來就要 include <algorithm>，不必多背一個名字（上冊 7.6 的 swap 也是同一種情況）。

¶sort 有多快？

sort 的運算量是 O(n \log n) 等級（O 記號與估時三步驟見 10.1；\log 是什麼，17.6 會用「一直除以 2」帶你直觀認識）。直接看數字最有感——下面是在 AACPOJ 的伺服器上實測排序隨機整數所花的時間：

兩件事值得注意。第一，資料量乘以 10，時間大約也只乘以 10 出頭（不是 100）——這就是 O(n \log n) 摸得到的樣子。第二，同一台機器上，10^5 個數字用本單元後面要學的泡沫排序（11.10，O(n^2)）要花將近 10 秒，sort 只要 0.005 秒——差了快兩千倍。一般題目給的資料量，對 sort 來說都是小菜。

（時間會隨機器、資料內容而有出入，換一台電腦跑出不一樣的秒數很正常；要記住的是量級，不是小數點後幾位。）

預設順序「由小到大」的依據是元素型態的 <：整數比大小、字元比 ASCII 編號（8.1）、string 比字典序（10.8）、pair 先比 first 再比 second（10.11）——所以只要是能用 < 比較的型態，sort 都能排。

動手試試看：解掉葫蘆判定——5 張牌組成「某數恰出現 3 次＋另一數恰出現 2 次」才算葫蘆。亂序時要分好多情況；先 sort(a, a + 5) 呢？排完之後，葫蘆只可能長成「前三張同＋後兩張同」或「前兩張同＋後三張同」兩種樣子，兩個 if 收工——排序讓分類討論塌縮，正是 11.1 說的「排完等於解完一大半」。