※ 引述《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)