0

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

4

1 回答 1

1

是的，尽管在最坏的情况下（实际上数据没有类似排序），这将导致排序变慢。

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

一旦你的第一个列表被排序，索引列表实际上是一个指向原始未排序列表的指针。所以，如果我们有firstunsorted, firstsorted, and indexes, 那么对于任何ifrom0到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)比较，这是您可以得到的最好的。

于 2013-09-18T16:22:18.233 回答