0

我正在做一项家庭作业，其中要求我找到修改后的冒泡排序对大小为n的数据集进行的比较次数。要考虑的数据集是一个排序列表，其中第一个和最后一个元素被交换，例如：52341。下面是算法的伪代码：

i <- n-1; new_i <- i
while i > 0 do 
    for j=1 to i do
        if A[j] > A[j+1] do
            A[j] <=> A[j+1]
            new_i <- j
        endif
    endfor
    i <- new_i - 1; new_i <- i
endwhile

A 是数据集，<=> 是交换。

我试图找到一种方法来表示该算法，并将求和简化为对给定类型数据集的比较量的表达式。

没有给出答案，有人能把我推向正确的方向吗？

4

1 回答 1

2

在您的 Bubblesort 实现中，比较次数完全由输入的大小单独决定，即输入列表中元素的顺序无关紧要。

如果你能证明这一点（这不是很难），计算一个大小为 N 的输入列表的比较次数就足够了。由于我们已经证明顺序无关紧要，这又相当容易：

我们有两个循环，外while循环和内循环for循环。外部循环从 n 到 1（或 n-1 到 0，但肯定不是从 n-1 到 1，正如您的代码所建议的那样），即我们有 N 次迭代。内循环从 1 到 i。

因此，我们在外循环的第一次迭代中进行了 N 次比较，第二次进行了 N-1 次比较，第三次进行了 N-2 次比较，...，第 NN 次进行了 0 次比较。

我想你是一个人走到这一步的。否则，无论如何，你都被搞砸了。

您的老师现在想看到的是您知道以下公式，即所谓的“Gaußsche Summenformel”，也称为“Gauss Sum”：

N + (N-1) + (N-2) + ... + (N-N+1) + (NN) = N^2/2 + N/2

所以你应该在这里做的是：

  • 表明比较次数仅取决于输入的大小
  • 表明比较次数等于 N + (N-1) + (N-2) + ... + (N-N+1) + (NN)
  • 提到这和N^2/2 + N/2一样，指的是Mr. Gauß。

;-)

于 2012-09-21T11:18:06.847 回答