問題(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甚至也可以根本就不存, 要用到排序數列時再算出來就好了