※ 引述《angelina877 (牛牛)》之銘言：
: 問題(Question)：
: 我們都學過很多排序演算法,
: 如Bubble Sort,Merge Sort,Insert Sort
: 今天,小妹有一個問題
: 就是如何在已經排好的數列中,去回復原始資料,
: 請問有這種演算法嗎? 我找了一段時間 沒找到
: EX
: 原始資料
: [1,1,0,1,1,0,0]
: 1.使用演算法 得到排序資料
: [0,0,0,1,1,1,1]
: 2.再從排序資料中回復成原始資料
: [1,1,0,1,1,0,0]
: 補充說明(Supplement)：
: 我找了好多天了,實在是挫折連連
: 逼不得已才上來問QAQ
: 希望高手相救XDD
目前感覺merge sort可以比較簡單做
merge sort不要線性排序在小區間優化
可以把那個排序倒金字塔是否有交換做記號
1 4 3 7 6 2 5
1 4 3 7 6 2 5
1 4 3 7 6 2 5
1 4 3 7 6 2 5
從這步開始記錄 左邊的元素推入記0 右邊元素推入記1
0 1 0 1 1 0 0
1 4 3 7 2 6 5
0 1 0 1 0 1 0
1 3 4 7 2 5 6
0 1 0 0 1 1 0
1 2 3 4 5 6 7
總共記下
0101100
0101010
0100110
還原時
0 1 0 0 1 1 0
1 2 3 4 5 6 7
把對應到0的放到左邊 1的右邊
0 1 0 1 0 1 0
1 3 4 7 2 5 6
依此類推。
這方法每一步都要儲等同資料量的bits數
設資料量n
所需空間為 n bits * log(n)