耐心排序

耐心排序（Patience Sort）是将数组的元素分类成很多堆再串接回数组的一种排序算法。

操作解说

• 创建一个堆数组
• 比较目前指向的元素和每个堆的第一个元素，计算出比目前元素小的堆数量
• 若目前元素比所有堆的第一个元素大，创建新的堆并加入到堆数组中，否则将目前元素加入到第“比目前元素小的堆数量”个堆
• 分类完后将每个堆反序然后对每个堆再做耐心排序
• 最后将每个堆串接并存储回原本的数组

演示操作一次耐心排序分堆过程

假设目前欲排序的数列为: 3, 5, 7, 1, 4

Step 1: 取出数字 3, 由于目前没有任何堆所以产生一号堆并把 3 放入

• 堆 一
  • 内容: 3

Step 2: 取出数字 5, 5 比一号堆的第一个数字 3 大, 故产生二号堆并把 5 放入

• 堆 一
  • 内容: 3
• 堆 二
  • 内容: 5

Step 3: 取出数字 7, 7 比一号堆和二号堆的第一个数字大, 故产生三号堆并把 7 放入

• 堆 一
  • 内容: 3
• 堆 二
  • 内容: 5
• 堆 三
  • 内容: 7

Step 4: 取出数字 1, 所有堆的第一个数字都比 1 大, 故放入一号堆

• 堆 一
  • 内容: 3, 1
• 堆 二
  • 内容: 5
• 堆 三
  • 内容: 7

Step 5: 取出数字 4, 只有一号堆的第一个数字比 4 小, 所以将 4 放入二号堆

• 堆 一
  • 内容: 3, 1
• 堆 二
  • 内容: 5, 4
• 堆 三
  • 内容: 7

实现示例

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);
        else
            piles[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;
}

Python 3.10

def to_piles(arr: list) -> list:
    if len(arr) == 1:
        return arr

    piles: list = []
    for a in arr:
        if not piles:
            piles.append([a])
            continue

        for pile in piles:
            if pile[0] > a:
                pile.append(a)
                break
        else:
            piles.append([a])

    return piles

def patience_sort(arr: list):
    piles: list = to_piles(arr)
    is_sorted: bool = True
    while is_sorted:
        temp_piles: list = []
        is_sorted = False

        for pile in piles:
            if len(pile) == 1:
                temp_piles.append(pile)
                continue

            is_sorted = True
            pile.reverse()
            temp_piles += to_piles(pile)

        piles.clear()
        piles += temp_piles

    arr.clear()
    arr += [pile[0] for pile in piles]

if __name__ == '__main__':
    arr = [3, 7, 5, 1, 3, 6, 4, 0, 8, 2]
    patience_sort(arr)
    print(arr)

原文地址：https://zh.wikipedia.org/wiki/%E8%80%90%E5%BF%83%E6%8E%92%E5%BA%8F

在知识共享 署名-相同方式共享 3.0协议之条款下提供