这种晦涩难懂的排序算法怎么称呼

Question

我想出了一个晦涩的排序算法，鉴于它如此简单，它一定是以前发明和命名的，所以我想知道它叫什么。

它有一个非常罕见的约束：它仅适用于具有从0to n-1（或等效键）键的输入。这是一个非常强的约束，使其在实践中毫无用处，但也许我们可以构建一些让它有用的人为设置。该算法基本上将特定位置的元素与其最终位置交换，直到数组排序为止。伪代码：

def obscure_sort(array):
  sorted_until = 1
  while true
    if key(array[0]) != 0:
      # Swap the element at position 0 to its final position.
      swap(array, 0, key(array[0]))
    else:
      # Find the next element that isn't in its final position.
      while key(array[sorted_until]) == sorted_until:
        sorted_until++
        # If we happen to reach the end, we're done.
        if sorted_until == array.length:
          return
      # Swap the newfound first unsorted element to position 0
      swap(array, 0, sorted_until)

该算法实际上运行在O(n). 看到这一点并不完全是微不足道的，除非有人真的感兴趣，否则我将省略分析。

有谁知道这个有名字吗？

Answer 1

这是限制循环排序的一个细微变化，可能最接近本文第 3 节中的算法。

通常，通过对键进行循环排序A = [0, 1,...(A.length-1)]，您将循环遍历数组测试索引0 to A.length-1作为“循环开始”，寻找要旋转的循环。一次“旋转”是通过始终保存临时变量“temp”（最初是我们的循环开始）并执行 aswap(temp, A[temp])直到我们回到循环开始时（即，当 temp == A[temp] 时）来完成的。

相比之下，这里我们在循环后面添加 0，并用“A[0]”代替“temp”。我们使用操作swap(A[0], A[A[0]])，因此一般来说，移动的元素 x 会经历 A[old] -> A[0] -> A[x] 的旅程，而不是 A[temp] -> temp -> A[x] 。

在上述论文中描述的线性时间算法中，在开始循环迭代时i，所有元素0, 1, ..., i-1都就位并且不再移动。这个算法是类似的，除了如果它是用相同的循环风格编写的，0, 1, ..., i-1也在迭代开始时就位，i但元素 0 不固定，在迭代期间不断移动。

举一个小例子：

Traditional Cycle Sort
Initially, A = [1, 3, 0, 2]

Step 1: A = [1, 3, 0, 2], temp = 1, with cycle_start = 0
Step 2: A = [1, 1, 0, 2], temp = 3
Step 3: A = [1, 1, 0, 3], temp = 2
Step 4: A = [2, 1, 2, 3], temp = 0
Step 5: A = [0, 1, 2, 3], temp = 2; stop since temp == A[temp]

Custom Cycle-like Sort
A = [1, 3, 0, 2]

Step 1: A = [1, 3, 0, 2]
Step 2: A = [3, 1, 0, 2]
Step 3: A = [2, 1, 0, 3]
Step 4: A = [0, 1, 2, 3]

请注意，这种新排序可以比正常循环排序采取更多步骤，因为“在循环后面添加 0”可以在每个循环中添加额外的交换操作。不过，数组交换的总数是线性的（最多是数组长度的两倍）。