algorithm - 优化循环排序实现

Question

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

有什么方法可以提高 code on 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

Answer 1

此算法的昂贵部分是找出每个项目的去向。其余部分只是一次一个循环地应用排列。此代码用 O(n^2) 计算出元素的去向，用 O(n) 实际移动它们。

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

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