我想对很多数组进行排序,它们的大小都大致相同,比如说 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