问题(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

如果只有1跟0我只想到转成10进制记下总和 再回推回去

排序通常不会记录排序过程资料，除非另外记录，要不然不可能从排序后资料反推原始资料吧要记录过程不如直接复制一份原始资料Prob_Solve 或者 Programming 这两个版可以问看看

为什么不记原始资料就好了

...排序前复制一份不就好了

记原始不就得了 不然你要记排序的情况吗?

我以前曾经写一个程式是加一个 index，排序时只排index 的阵列，没有动到原始的资料，这样同样的资料可以做好几种排序，只要加一个 index 就有一种排序。只是好像与原 po 的需求不太符合，sorry，胡言乱语。

有多种原始资料可以得到妳的排序资料 要回到哪一种?

有 10! 种输入排好后会变成 1 2 3 4 5 6 7 8 9 10

我想原po大概是很单纯的想做 stack rollback 动作而已吧把排序的过程纪录下来，到时再反推回去，这样不行吗 ?这动作就是我上面说的 stack rollback (不知道正不正式.)

真的要记用楼上的方法应该是最省memory的P.S 排好的不需要存 记0跟1的数量就好

看样子应该是问到一个很难的技术 或者不可能解决= =排序过程记下来 那要怎么记 刚刚纪录的东西越少越好

小于 2n 是怎样的概念? 那 2n - 1 呢 ?

有1*n个序列，原图加排序后，不是(1*n)*2=2*n吗？2^n是等比级数膨胀的吧

纪录大小 < n 我觉得不太可能 , 扣除计数式排序 , 最快是 O(n logn) , 若每次纪录的是交换的两个索引 (i,j),那大小估算大概也要 2 * n * log(n)等等... 插入排序应该只要 2*n 就行了...讲错，是交换排序 Orz , 插入排序还没想空间需求

五百块咧 我给你算了

是不是只要还原成原本的样子就可以?不用中间的过程

我是有想到可以省1,2bits的方法，不过很鸟～～～例如a[0,0,1,1,1,1,0,1] b[0,0,1,1,1,1,0] 少的bit就补1，这样可以偷工减料少记录1bit如果运气好 a[0,0,1,1,0,0,1,1]，则b[0,0,1,1,0,0]则可以偷工减料2bits XD 运气不好就.......

总觉得这样就不要动原始资料，只要分别记 0, 1 的个数就是排序的结果了。这样算花 2*log n bits 吗？

a[0,0,1,1,1,1,0,1] b[0,0,0]，话说这样根本就连排序都不用了，直接算0的个数就是结果＠＠

怎么听起来比较像数数+压缩阿把一堆压缩算法都拿来试试看阿XD

popcount?

那就原序列不要动, 只算总共几个 0 or 1 最多用 4bits不过原序列都用掉 8bits 了, 省这几 bits 让人费解 R甚至也可以根本就不存, 要用到排序数列时再算出来就好了