在計算機科學中，耐心排序（Patience Sort）是將數組的元素分類成很多堆再串接回數組的一種排序算法。受到紙牌遊戲耐心的啟發和命名。算法的變體有效地計算給定陣列中最長的增加子序列的長度。
基本介紹
- 中文名：耐心排序
- 外文名：Patience Sort
- 本質：一種排序算法
簡介,歷史,實現示例,
簡介
- 創建一個堆數組
- 比較當前指向的元素和每個堆的第一個元素，計算出比當前元素小的堆數量
- 若當前元素比所有堆的第一個元素大，創建新的堆並加入到堆數組中，否則將當前元素加入到第“比當前元素小的堆數量”個堆
- 分類完後將每個堆反序然後對每個堆再做耐心排序
- 最後將每個堆串接並存儲回原本的數組
耐心分類與稱為弗洛伊德遊戲的紙牌遊戲密切相關。 這個遊戲非常類似於之前描繪的遊戲：
發出的第一張牌形成一張由單張牌組成的新牌。
每張後續卡片放置在一些現有的堆上，其頂部卡的值不大於新卡的值，或者放在所有現有樁的右側，從而形成新的堆。
當沒有剩餘的牌可以交換時，遊戲結束。
遊戲的目標是儘可能少地完成遊戲。 與耐心排序算法的不同之處在於，不需要在允許的最左邊的堆上放置新卡。 耐心分類構成了玩這個遊戲的貪婪策略。
Aldous和Diaconis建議將9個或更少的樁定義為n = 52的獲勝結果，其發生機率約為5%。
用於找到最長增加子序列的算法
首先，執行如上所述的排序算法。 樁的數量是最長子序列的長度。 每當一張牌放在一堆紙上時，將一個後指針放在前一堆的頂牌上（假設它具有比新牌更低的價值）。 最後，按照最後一堆中頂部牌的反向指針來恢復最長長度的遞減子序列; 它的反向是對增長最長的子序列算法的回答。
S. Bespamyatnikh和M. Segal描述了算法的有效實現，不會產生額外的漸近成本（因為後向指針存儲，創建和遍歷需要線性時間和空間）。 他們進一步展示了如何報告來自相同結果數據結構的所有最長的增長子序列。
歷史
耐心分類由C. L. Mallows命名，他將其發明歸功於A.S.C. 羅斯在20世紀60年代初。根據Aldous和Diaconis，耐心排序首先被認為是計算Hammersley和A.S.C.計算最長的子序列長度的算法。 Ross和獨立的Robert W. Floyd作為排序算法。 初步分析由Mallows完成。弗洛伊德的比賽由弗洛伊德與唐納德克努特通信開發。
實現示例
C++11
#include <iostream>#include <algorithm>#include <vector>using namespace std; template<typename T>vector<T>& operator<<(vector<T>& vi, vector<T>& vx) { //串接陣列int len = vi.size();vi.resize(vi.size() + vx.size());for (int i = 0; i < (int) vx.size(); i++)vi[i + len] = vx[i];return vi;}template<typename T>void reverse(vector<T>& arr) { //陣列反序int len = arr.size();for (int i = 0; i < len - 1 - i; i++)swap(arr[i], arr[len - 1 - i]);} template<typename T>void patience_sort(vector<T>& arr) {int len = arr.size();if (len < 2)return;vector<vector<T> > piles;for (int i = 0; i < len; i++) { //將陣列元素分堆vector<T> new_pile = { arr[i] };int insert;for (insert = 0; insert < (int) piles.size(); insert++) //計算當前元素比多少個堆陣列第一個元素還大if (new_pile[0] < piles[insert][0])break;if (insert == (int) piles.size())piles.push_back(new_pile);elsepiles[insert].push_back(arr[i]);}arr.clear();for (int j = 0; j < (int) piles.size(); j++) {reverse(piles[j]); //因為排出來的堆陣列第一個元素是該陣列最大值，故要反序patience_sort(piles[j]);arr << piles[j]; //串接陣列}} template<typename T>ostream& operator<<(ostream& os, vector<T> v) { //顯示陣列內容int len = v.size();for (int i = 0; i < len; cout << (++i == len ? "" : ","))os << v[i];return os;} int main() {vector<int> arr = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };cout << arr << endl;patience_sort(arr);cout << arr << endl;return 0;}