cpp sort
1.16.0 — Taxonomics
如果只有一種或兩種排序方法能夠支配所有其他方法，無論使用什麼應用程式或計算機，那就太好了。但事實上，每種方法都有其獨特的優點。 [...] 因此，我們發現幾乎所有的演算法都值得被記住，因為在某些應用中它們被證明是最好的。 — Donald Knuth，《電腦程式設計藝術》，第 3 卷
cpp-sort是一個通用的 C++14 僅頭檔排序庫。它圍繞著一個主要的通用排序介面，並提供幾個小工具來選擇和/或設計排序演算法。使用它的基本排序功能應該很簡單：
# include < array >
# include < iostream >
# include < cpp-sort/sorters/smooth_sorter.h >
int main ()
{
std::array< int , 5 > arr = { 5 , 8 , 3 , 2 , 9 };
cppsort::smooth_sort (arr);
// prints 2 3 5 8 9
for ( int val: arr) {
std::cout << val << ' ' ;
}
}cpp-sort提供了一整套與排序相關的功能。以下是該庫的主要構建塊：
下面是一個更完整的範例，說明了可以使用該程式庫完成哪些操作：
# include < algorithm >
# include < cassert >
# include < forward_list >
# include < functional >
# include < vector >
# include < cpp-sort/adapters.h >
# include < cpp-sort/sorters.h >
int main ()
{
struct wrapper { int value; };
std::forward_list<wrapper> li = { { 5 }, { 8 }, { 3 }, { 2 }, { 9 } };
std::vector<wrapper> vec = { { 5 }, { 8 }, { 3 }, { 2 }, { 9 } };
// When used, this sorter will use a pattern-defeating quicksort
// to sort random-access collections, and a mergesort otherwise
cppsort::hybrid_adapter<
cppsort::pdq_sorter,
cppsort::merge_sorter
> sorter;
// Sort li and vec in reverse order using their value member
sorter (li, std::greater<>{}, &wrapper::value);
sorter (vec, std::greater<>{}, &wrapper::value);
assert ( std::equal (
li. begin (), li. end (),
vec. begin (), vec. end (),
[]( const auto & lhs, const auto & rhs) { return lhs. value == rhs. value ; }
));
}即使在沒有額外功能的情況下使用排序函數，它們仍然提供一些有趣的保證（通常取自 Ranges TS 的想法）：
iter_swap和iter_move正確處理代理迭代器operator()轉換為函數指針您可以閱讀有關所有可用工具的更多信息，並在 wiki 中找到一些有關使用和擴展cpp-sort 的教程。
下圖是使用基準目錄中的腳本產生的。它顯示了heap_sort在不進行調整的情況下對一百萬個元素進行排序所需的時間，以及使用drop_merge_adapter或split_adapter進行調整時所需的時間。
如上所示，使用任一轉接器包裝heap_sort使其能夠以非侵入方式適應反轉數量。用來適應它的演算法有不同的優點和缺點，這取決於你使用哪一種。
這個基準主要是為了展示圖書館提供的可能性。您可以在專門的 wiki 頁面中找到更多此類評論基準。
cpp-sort需要 C++14 支持，並且應與以下編譯器配合使用：
/permissive- 。有些功能不可用。上面列出的編譯器是 CI 管道使用的編譯器，而該程式庫也定期使用這些編譯器的最新版本進行測試。中間的所有其他編譯器版本都未經測試，但也應該可以工作。如果情況並非如此，請隨意提出問題。
庫中的功能可能會有所不同，具體取決於所使用的 C++ 版本和啟用的編譯器擴充。這些變更記錄在 wiki 中。
主存儲庫包含 CMake 或 Conan 等標準工具的附加支援。您可以在 wiki 中閱讀更多相關內容。
我有一輛新車。我只需要把它放在一起。它們更容易被一塊一塊地偷走。 — 賈羅德金茨，3.33 美元
Even though some parts of the library are original research and some others correspond to custom and rather naive implementations of standard sorting algorithms, cpp-sort also reuses a great deal of code and ideas from open-source projects, often altered to integrate seamlessly into the圖書館.以下是用於建立該庫的外部資源的清單。我希望許多不同的許可證是相容的。如果不是這種情況，請聯絡我（或提交問題），我們將看看可以採取什麼措施：
insertion_sorter和pdq_sorter使用的一些演算法來自 Orson Peters 的模式擊敗快速排序。基準測試的某些部分也來自那裡。
tim_sorter使用的演算法來自 Goro Fuji 的 Timsort 實作 (gfx)。
spread_sorter使用的三種演算法來自Steven Ross Boost.Sort模組。
d_ary_spread_sorter使用的演算法來自 Tim Blechmann 的 Boost.Heap 模組。
spin_sorter使用的演算法來自 Boost.Sort 中實作的同名演算法。作者：弗朗西斯科·何塞·塔皮亞。
utility::as_function 、 utility::static_const和幾個投影增強輔助演算法來自 Eric Niebler 的 Range v3 函式庫。代理迭代器、定制點和投影等一些想法以及一些其他實用函數也來自該庫或相關文章和標準 C++ 提案。
ska_sorter使用的演算法來自 Malte Skarupke 對他自己的 ska_sort 演算法的實作。
drop_merge_sorter所使用的演算法來自 Adrian Wielgosik C++ 對 Emil Ernerfeldt 的 drop-merge sort 的重新實作。
許多增強的標準演算法直接改編自 libc++ 中的對應演算法，並經過增強以處理投影和代理迭代器。
該庫內部使用與前向迭代器一起使用的inplace_merge函數。它的實現使用了 Dudziński 和 Dydek 提出的合併演算法，並由 Alexander Stepanov 和 Paul McJones 在他們的《程式設計元素》一書中實現。
當沒有足夠的記憶體來執行異地合併時，隨機存取迭代器的inplace_merge重載使用 Pok-Son Kim 和 Arne Kutzner 在透過對稱比較穩定最小儲存合併中提出的Symmerge演算法。
smooth_sorter所使用的 Dijkstra 平滑排序的實作直接改編自 Keith Schwarz 的演算法實作。
wiki_sorter使用的演算法改編自 BonzaiThePenguin 的 WikiSort。
grail_sorter使用的演算法改編自 Mrrl 的 GrailSort。
具有前向或雙向迭代器的indirect_adapter所使用的演算法是Matthew Bentley 的indiesort 的稍微修改版本。
某些演算法使用的nth_element隨機存取重載的實作來自 Danila Kutenin 的 miniselect 函式庫，並使用 Andrei Alexandrescu 的AdaptiveQuickselect演算法。
sorting_network_sorter所使用的排序網路都來自Bert Dobbelaere維護的這個清單。該頁面引用了它列出的所有排序網絡的來源。
sorting_network_sorter使用的一些優化來自 StackOverflow 上的討論，並且得到文章應用排序網路來綜合優化排序庫的支援。
此測試套件重新實現了最初在以下位置找到的隨機數演算法：
用於繪製排序網路的 LaTeX 腳本是 kaayy 的sortingnetwork.tex的修改版本，稍微修改為基於 0 並從上到下繪製網路。
專案中嵌入的 CMake 工具包括來自 RWTH-HPC/CMake-codecov 和 Crascit/DownloadProject 的腳本。
一些基準測試使用 Thøger Rivera-Thorsen 開發的色盲友善調色板。
