无限交换排序算法

Question

我想就我在教科书中发现的以下问题得到一些帮助。

sort (array[], nr_of_item)
{
   while(true)
     i:=value from an n-sided fair dice roll
     j:=value from an n-sided fair dice roll
     if (i > j)
       swap i and j
     if (array[i] > array [j])
       swap array[i] and array[j]
     end while
}

现在，它说它没有描述正确的算法。但是他们说：

一段时间后，应该对数组进行排序，并证明如果输入未排序，则对数组进行排序的比较次数为O（n^3）。

另一个问题是：

验证算法是否会在O（n）时间内对数组进行排序

我真的不明白你怎么能证明这一点，因为i和j是随机的。

Answer 1

i和j指的是索引，j总是调整为两者中的较大值。这意味着由索引i指定的元素（表示为x）将位于元素左侧的索引j，表示为y。

然后，仅当y和x未排序时，才交换元素，这意味着x大于y，并且根据它们的索引位置，位于y的左侧，因此是无序的。这保证了函数只会更接近（而不是更远）排序状态。

现在，关于复杂性，想象一下气泡排序，它被设计为在数组中迭代，而不是随机进行选择。这有一个n平方的复杂度。不过，这里还发生了其他事情。你随机选择两个元素，因此n-choose-1倍于冒泡排序的复杂度，变成n次方。

函数的每次调用都会进行两次比较，特别是2次比较。因此，复杂度是n立方乘以2，可以用大O表示法表示为n立方。