跳转至

排序相關 STL

本頁面將簡要介紹 C 和 C++ 標準庫中實現的排序算法。

除已説明的函數外，本頁所列函數默認定義於頭文件 <algorithm> 中。

qsort

參見：qsort，std::qsort

該函數為 C 標準庫實現的 快速排序，定義在 <stdlib.h> 中。在 C++ 標準庫裏，該函數定義在 <cstdlib> 中。

qsort 與 bsearch 的比較函數

qsort 函數有四個參數：數組名、元素個數、元素大小、比較規則。其中，比較規則通過指定比較函數來實現，指定不同的比較函數可以實現不同的排序規則。

比較函數的參數限定為兩個 const void 類型的指針。返回值規定為正數、負數和 0。

比較函數的一種示例寫法為：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int compare(const void *p1, const void *p2)  // int 類型數組的比較函數
{
  int *a = (int *)p1;
  int *b = (int *)p2;
  if (*a > *b)
    return 1;  // 返回正數表示 a 大於 b
  else if (*a < *b)
    return -1;  // 返回負數表示 a 小於 b
  else
    return 0;  // 返回 0 表示 a 與 b 等價
}

注意：返回值用兩個元素相減代替正負數是一種典型的錯誤寫法，因為這樣可能會導致溢出錯誤。

以下是排序結構體的一個示例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
struct eg  // 示例結構體
{
  int e;
  int g;
};

int compare(const void *p1,
            const void *p2)  // struct eg 類型數組的比較函數：按成員 e 排序
{
  struct eg *a = (struct eg *)p1;
  struct eg *b = (struct eg *)p2;
  if (a->e > b->e)
    return 1;  // 返回正數表示 a 大於 b
  else if (a->e < b->e)
    return -1;  // 返回負數表示 a 小於 b
  else
    return 0;  // 返回 0 表示 a 與 b 等價
}

這裏也可以看出，等價不代表相等，只代表在此比較規則下兩元素等價。

std::sort

參見：std::sort

用法：

1
2
3
4
5
6
// a[0] .. a[n - 1] 為需要排序的數列
// 對 a 原地排序，將其按從小到大的順序排列
std::sort(a, a + n);

// cmp 為自定義的比較函數
std::sort(a, a + n, cmp);

注意：sort 的比較函數的返回值是 true 和 false，用 true 和 false 表示兩個元素的大小（先後）關係，這與 qsort 的三值比較函數的語義完全不同。具體內容詳見上方給出的 sort 的文檔。

如果要將 sort 簡單改寫為 qsort，維持排序順序整體上不變（不考慮等價的元素），需要將返回 true 改為 - 1，返回 false 改為 1。

std::sort 函數是更常用的 C++ 庫比較函數。該函數的最後一個參數為二元比較函數，未指定 cmp 函數時，默認按從小到大的順序排序。

舊版 C++ 標準中僅要求它的 平均 時間複雜度達到 \(O(n\log n)\)。C++11 標準以及後續標準要求它的 最壞 時間複雜度達到 \(O(n\log n)\)。

C++ 標準並未嚴格要求此函數的實現算法，具體實現取決於編譯器。libstdc++ 和 libc++ 中的實現都使用了 內省排序。

std::nth_element

參見：std::nth_element

用法：

1
2
std::nth_element(first, nth, last);
std::nth_element(first, nth, last, cmp);

它重排 [first, last) 中的元素，使得 nth 所指向的元素被更改為 [first, last) 排好序後該位置會出現的元素。這個新的 nth 元素前的所有元素小於或等於新的 nth 元素後的所有元素。

實現算法是未完成的內省排序。

對於以上兩種用法，C++ 標準要求它的平均時間複雜度為 \(O(n)\)，其中 n 為 std::distance(first, last)。

它常用於構建 K-D Tree。

std::stable_sort

參見：std::stable_sort

用法：

1
2
std::stable_sort(first, last);
std::stable_sort(first, last, cmp);

穩定排序，保證相等元素排序後的相對位置與原序列相同。

時間複雜度為 \(O(n\log (n)^2)\)，當額外內存可用時，複雜度為 \(O(n\log n)\)。

std::partial_sort

參見：std::partial_sort

用法：

1
2
3
// mid = first + k
std::partial_sort(first, mid, last);
std::partial_sort(first, mid, last, cmp);

將序列中前 k 元素按 cmp 給定的順序進行原地排序，後面的元素不保證順序。未指定 cmp 函數時，默認按從小到大的順序排序。

複雜度：約 \((\mathit{last}-\mathit{first})\log(\mathit{mid}-\mathit{first})\) 次應用 cmp。

原理：

std::partial_sort 的思想是：對原始容器內區間為 [first, mid) 的元素執行 make_heap() 操作，構造一個大根堆，然後將 [mid, last) 中的每個元素和 first 進行比較，保證 first 內的元素為堆內的最大值。如果小於該最大值，則互換元素位置，並對 [first, mid) 內的元素進行調整，使其保持最大堆序。比較完之後，再對 [first, mid) 內的元素做一次堆排序 sort_heap() 操作，使其按增序排列。注意，堆序和增序是不同的。

自定義比較

參見：運算符重載

內置類型（如 int）和用户定義的結構體允許定製調用 STL 排序函數時使用的比較函數。可以在調用該函數時，在最後一個參數中傳入一個實現二元比較的函數。

對於用户定義的結構體，對其使用 STL 排序函數前必須定義至少一種關係運算符，或是在使用函數時提供二元比較函數。通常推薦定義 operator<。1

示例：

1
2
3
4
int a[1009], n = 10;
// ...
std::sort(a + 1, a + 1 + n);                  // 從小到大排序
std::sort(a + 1, a + 1 + n, greater<int>());  // 從大到小排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
struct data {
  int a, b;

  bool operator<(const data rhs) const {
    return (a == rhs.a) ? (b < rhs.b) : (a < rhs.a);
  }
} da[1009];

bool cmp(const data u1, const data u2) {
  return (u1.a == u2.a) ? (u1.b > u2.b) : (u1.a > u2.a);
}

// ...
std::sort(da + 1, da + 1 + 10);  // 使用結構體中定義的 < 運算符，從小到大排序
std::sort(da + 1, da + 1 + 10, cmp);  // 使用 cmp 函數進行比較，從大到小排序

嚴格弱序

另請參閲：C++ 中的應用 - 序理論

進行排序的運算符必須滿足 嚴格弱序，否則會出現不可預料的情況（如運行時錯誤、無法正確排序）。

常見的錯誤做法：

  • 使用 <= 來定義排序中的小於運算符。
  • 在調用排序運算符時，讀取外部數值可能會改變的數組（常見於最短路算法）。
  • 將多個數的最大最小值進行比較的結果作為排序運算符（如皇后遊戲/加工生產調度 中的經典錯誤）。

外部鏈接

參考資料與註釋

  1. 因為大部分標準算法默認使用 operator< 進行比較。 ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用