python - 重用已知的排序操作对类似未排序的数据进行排序

Question

我想对大量数组进行排序，所有数组的大小都大致相同，比方说 30 个元素，并且大部分顺序相同。 鉴于我知道一个数组的排序顺序，将其称为模板并假设它与所有其他数组非常相似，我如何利用这些知识快速对其余数组进行排序？

与我们选择的模板相比，大多数数组只会缺失或多出一两个(很少更多)值。

我想避免使用已知顺序填充临时数组并对其应用通用排序算法的方法。事实上，我希望能够简单地按排序顺序读取数组并针对少数无序元素进行调整(并且我非常愿意解释为什么这不可能或可能不可能)。

这似乎是一个已知问题，是否已经有通用算法来实现这一点？

这是基本思想(编辑:但在这个例子中，第二个数组的排序顺序和大小完全相同。在实际情况下，其他数组不是 相同，大小和顺序略有不同):

#begin with some random values
data = [13, 23, 41, 69, 12, 53, 63, 23, 25, 14, 37, 2, 39, 42, 99, 71, 91]
data_id = [(y, x) for x, y in enumerate(data)] #create pairs: (value, index)
s_data_id = sorted(data_id) #sort by value
s_data, s_order = zip(*s_data_id) #extract the sorted value and the index each came from

print "Sorted:", s_data
print "Order:", s_order

#other random values in the same order as the first (just for example they are exactly the same)
otherdata = [13, 23, 41, 69, 12, 53, 63, 23, 25, 14, 37, 2, 39, 42, 99, 71, 91]

#sort these values using the same order from the initial sort
s_ortherdata = [otherdata[s_order[i]] for i in range(len(s_order))]

print "Resorted:", s_ortherdata

http://codepad.org/60sdEqUu

Answer 1

是的，尽管在最坏的情况下(实际上数据的排序方式不同)这会导致排序速度变慢。

从 0 的有序列表开始至 n-1 , 其中n是原始列表的长度。在对第一个列表进行排序时，每次移动或交换原始列表中的元素时，也会移动此列表中的相应元素，我将其称为索引列表。

一旦你的第一个列表被排序，索引列表实际上是一个指向原始未排序列表的指针。所以，如果我们有 firstunsorted , firstsorted , 和 indexes , 然后对于任何 i来自 0至 n-1 , firstsorted[i] == firstunsorted[indexes[i]] .

然后您可以使用这些索引以相同的方式“预排序”每个其他列表 - otherlist[i] = otherlistunsorted[indexes[i]]对于每个 i .

最后，选择具有良好最佳情况性能的第二种排序算法。例如，关于排序算法的维基百科页面推荐插入排序或 shellsort(如果你讨厌你的 CS 教授，或者冒泡排序!)。您的第二个排序过程将使用它来最终确定每个列表的排序。

我们不会通过进行此更改来添加任何比较 - 它仍然是 O(n log n)在初始排序的平均情况下，您只需要进行两倍的分配(构建 indexes )。在其他列表中，这在技术上并不比复制每个列表更糟糕，所以又多了一组 n。每个列表的分配和n log n对于第一个列表。另一方面，如果你是对的并且列表的排序完全相同，那么第一个列表之后的所有列表都不需要 O(n log n)。至 O(n)比较，这是你能得到的最好的。