耐心排序（）是將陣列的元素分類成很多堆再串接回陣列的一種排序演算法。注意「」一詞在此並非「耐心」之意，而是一種單人紙牌遊戲的名字（英文中又稱爲card solitaire）。
操作解說
- 建立一個堆陣列
- 比較目前指向的元素和每個堆的第一個元素，計算出比目前元素小的堆數量
- 若目前元素比所有堆的第一個元素大，建立新的堆並加入到堆陣列中，否則將目前元素加入到第「比目前元素小的堆數量」個堆
- 分類完後將每個堆反序然後對每個堆再做耐心排序
- 最後將每個堆串接並儲存回原本的陣列
演示操作一次耐心排序分堆過程
假設目前欲排序的數列為: 3, 5, 7, 1, 4
Step 1:
取出數字 3, 由於目前沒有任何堆所以產生一號堆並把 3 放入
- 堆 一
** 內容:
Step 2:
取出數字 5, 5 比一號堆的第一個數字 3 大, 故產生二號堆並把 5 放入
- 堆 一
** 內容: 3
- 堆 二
** 內容:
Step 3:
取出數字 7, 7 比一號堆和二號堆的第一個數字大, 故產生三號堆並把 7 放入
- 堆 一
** 內容: 3
- 堆 二
** 內容: 5
- 堆 三
** 內容:
Step 4:
取出數字 1, 所有堆的第一個數字都比 1 大, 故放入一號堆
- 堆 一
** 內容: 3,
- 堆 二
** 內容: 5
- 堆 三
** 內容: 7
Step 5:
取出數字 4, 只有一號堆的第一個數字比 4 小, 所以將 4 放入二號堆
- 堆 一
** 內容: 3, 1
- 堆 二
** 內容: 5,
- 堆 三
** 內容: 7
實作範例
C++11
#include
#include
#include
using namespace std;
template
vector& operator& vi, vector& vx) { //串接陣列
int len = vi.size();
vi.resize(vi.size() + vx.size());
for (int i = 0; i
void reverse(vector& arr) { //陣列反序
int len = arr.size();
for (int i = 0; i
void patience_sort(vector& arr) {
int len = arr.size();
if (len > piles;
for (int i = 0; i new_pile = { arr[i] };
int insert;
for (insert = 0; insert
ostream& operator v) { //顯示陣列內容
int len = v.size();
for (int i = 0; i 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
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)
其他連結
评论 (0)