1

循环排序是一种就地排序，它基于您正在排序的排列可以分解为循环的想法。如果您将每个循环旋转一个位置，则数组将被排序。这可以很容易地进行编码，以便对数组的写入次数是任何就地排序所需的理论最小值（这对于例如闪存驱动器上的大型数据集来说非常好，您希望在其中最大限度地减少写入次数设备）。

有什么方法可以提高Wikipedia 上代码的运行时间，同时保持其就地排序并保持最佳写入次数，或者它是最好的？

这是实现（注意range(a, b)从a到b - 1）：

# Sort an array in place and return the number of writes.
def cycleSort(array):
  writes = 0
  # Loop through the array to find cycles to rotate.
  for cycleStart in range(0, len(array) - 1):
    item = array[cycleStart]
    # Find where to put the item.
    pos = cycleStart
    for i in range(cycleStart + 1, len(array)):
      if array[i] < item:
        pos += 1
    # If the item is already there, this is not a cycle.
    if pos == cycleStart:
      continue
    # Otherwise, put the item there or right after any duplicates.
    while item == array[pos]:
      pos += 1
    array[pos], item = item, array[pos]
    writes += 1
    # Rotate the rest of the cycle.
    while pos != cycleStart:
      # Find where to put the item.
      pos = cycleStart
      for i in range(cycleStart + 1, len(array)):
        if array[i] < item:
          pos += 1
      # Put the item there or right after any duplicates.
      while item == array[pos]:
        pos += 1
      array[pos], item = item, array[pos]
      writes += 1
  return writes
4

1 回答 1

3

该算法的昂贵部分是弄清楚每个项目的去向。其余的只是一次应用一个排列一个周期。这段代码需要 O(n^2) 来确定项目的去向和 O(n) 来实际移动它们。

如果您愿意使用一些临时存储（例如 DRAM 而不是闪存），您可以通过使用临时指针数组、对其进行排序、然后使用结果来移动实际数据来加快速度。这就是在重复移动它们的成本过高的情况下对大型记录进行排序的方式。

如果不允许您拥有 O(n lg(n)) 位的辅助存储，我认为您可能不走运。仅记录要执行的排列需要 log(n!) = O(n lg(n)) 位的存储空间。因此，您需要逐步计算排列（就像 cycleSort 所做的那样），我看不出有任何方法可以廉价地做到这一点。

于 2010-10-04T17:54:26.007 回答