耐心排序

维基百科,自由的百科全书
跳转至: 导航搜索
耐心排序
分类 排序算法
数据结构 數組

耐心排序(Patience Sort)是將陣列的元素分類成很多堆再串接回陣列的一種排序演算法

操作解說[编辑]

  • 建立一個堆陣列
  • 比較目前指向的元素和每個堆的第一個元素,計算出比目前元素小的堆數量
  • 若目前元素比所有堆的第一個元素大,建立新的堆並加入到堆陣列中,否則將目前元素加入到第「比目前元素小的堆數量」個堆
  • 分類完後將每個堆反序然後對每個堆再做耐心排序
  • 最後將每個堆串接並儲存回原本的陣列

實作範例[编辑]

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;
}

其他連結[编辑]