Re: [問題] 排序演算法 可逆式

看板C_and_CPP作者 (天亮damody)時間10年前發表 (2014/10/21 18:35), 10年前編輯推噓0(001)
留言1則, 1人參與, 最新討論串4/6 (看更多)
※ 引述《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) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.129.168.106 ※ 文章網址: http://www.ptt.cc/bbs/C_and_CPP/M.1413916527.A.7D4.html ※ 編輯: damody (220.129.168.106), 10/22/2014 03:23:03

10/22 11:58, , 1F
只要存下原始資料 想逆幾步就逆幾步
10/22 11:58, 1F
文章代碼(AID): #1KHgTlVK (C_and_CPP)
討論串 (同標題文章)
文章代碼(AID): #1KHgTlVK (C_and_CPP)