有谁知道一种可逆的排序算法？所以鉴于此：
5,39,196,0,15,243
排序将创建：
0,5,15,39,196,243
然后在不需要知道任何知识的情况下反转它，除了可能使用了哪种排序算法以及运行了多少次迭代，它会回到：
5,39,196,0,15,243
我突然想到冒泡排序可能会奏效——只要我知道排序必须运行多少次，我可能只需将步骤反转该次数即可回到原来的状态。还有其他人吗？
这是一个实验，所以时间复杂度不是问题（我不在乎它有多慢）。
问问题
1381 次
2 回答
2
通常一个排序算法需要 n 个以上的步骤（通常是 O(nlogn)）来对 n 个项目进行排序。这意味着您最好保留副本（这只是 n < O(nlogn)）。
如果副本太多（对象太大），您可以按初始顺序保留一组引用（指针或 ID）。
于 2012-09-01T12:34:27.210 回答
2
如果您真的不关心运行时效率，可以使用Permutation Sort。
它将生成列表的所有排列，并检查哪个排列对列表进行了排序。如果您知道在找到排序列表之前已经运行了多少轮，那么您确切地知道为了到达那里而交换了哪些值。
如果您在未排序的列表上运行它并且必须运行 50 轮才能到达已排序的列表，您将确切地知道交换了哪些元素以到达那里并且可以反转排序。
于 2012-09-01T12:20:46.290 回答