arrays - 当比较不花时间时排序

Question

我想在这个成本模型下对数组 A 进行排序:

1. 对于任何值 x，A[i] = x 形式的赋值的成本为 1。此外，A[i] = A[j] 的成本为 1。

2. 其他操作，例如比较和赋值 for x = A[i](其中 x 不是数组中的位置)的成本为 0。

问题:

1. 给出对数组 A 进行排序所需的最坏情况时间的下限。你的答案应该是关于 n 的精确表达式，而不是使用渐近表示法。

2. 描述一个使用 O(n) 空间的排序算法。运行时间应与 1 中给出的下限完全匹配(完全匹配，而不是渐近匹配)。

3. 描述最适合此成本模型的就地排序算法。运行时应与 1 中给定的界限完全匹配(精确地，而不是渐近地)。

我的尝试:

1. n。这是因为，在最坏的情况下，数组的 n 个元素位于它们不应该位于的索引中。因此需要 n 次赋值才能按排序顺序获取数组。

2. 我的伪代码算法:

   def weird_sort(A):
       B = an array the same size of A
       C = an array of bools (default True) the same size of A
       for i in range(0, A.size):
           min = first index in c that is True
           for j in range(0, A.size):
               if (A[j] < A[min]) and (C[j]):
                   min = j
           B[i] = A[min]
           C[i] = False
       A = B
   

我相信这需要恰好 n 时间来运行，因为我们唯一一次将任何东西分配给 A 是在最后一行，我们将 B 的内容复制到 A。

1. 不知道从哪里开始。在我看来，为了将所有内容保持在原位，我们必须交换数组 A 中的内容，但我无法弄清楚如何使用 n/2 交换对数组进行排序。有人能让我朝着正确的方向前进吗？您也可以仔细检查我对 1 和 2 的回答吗？

Answer 1

我考虑就地允许 O(1) 额外的变量，否则我认为这是不可能的

首先让我们解决子问题:给定 i，找到应该在第 i 位置的数字。由于比较是免费的，因此可以使用暴力破解。

现在复制第一个元素(到附加变量)，找到最小的元素并将其放在位置 1。现在这个元素在位置 i。让我们找到应该在位置 i 的元素并将其复制到这里(假设它在位置 j)，现在找到属于位置 j 的元素> 等。最终我们找到了我们最初复制的元素，将其放回原处。因此，我们使用 k 赋值(在循环结构中)将 k 变量设置到它们的位置。 现在对所有其他元素执行相同的操作。您无法记住每个变量是否放置在其位置，但您可以免费检查它是否在其位置。

如果 A 中有相等的元素，这应该更小心地完成，但它应该仍然有效