指定 if 语句执行多少次【冒泡排序算法】

Question

1. for i=1 to n-1 do
2.    for j=1 to n-i do
3.       if a[j]>A[j+1] then
4.          Change A[j] with A[j+1]

告诉第 3 行（if 语句）中的指令将完成多少次。

我认为这是第一个未经修改的主要冒泡排序算法。
首先我会考虑三种情况：最好的、一般的和最差的。

在最好的方式中，if 语句将执行 n-1 次。数组中的数据将已经被隔离。遍历数组和结束算法就足够了。

在最坏的情况下，if 语句将完成：

<a href="http://www.codecogs.com/eqnedit.php?latex=\sum_{i=1}^{n-1}\tfrac{n(n-1)}{2}" target="_blank"><img src="http://latex.codecogs.com/gif.latex?\sum_{i=1}^{n-1}\tfrac{n(n-1)}{2}" title="\sum_{i=1}^{n-1}\tfrac{n(n-1)}{2}" /></a>

次。数组中的数据不会被隔离，每个位置都会被交换。

在平均情况下，if语句将完成：

<a href="http://www.codecogs.com/eqnedit.php?latex=\sum_{i=1}^{n-1}\tfrac{n(n-1)}{4}" target="_blank"><img src="http://latex.codecogs.com/gif.latex?\sum_{i=1}^{n-1}\tfrac{n(n-1)}{4}" title="\sum_{i=1}^{n-1}\tfrac{n(n-1)}{4}" /></a>

次？我认为那是因为它是最坏的情况除以 2。

我想请你看看我的想法是否正确。如果你觉得我说的不对请指正。

你好，

Answer 1

您的代码中没有检查数组是否已排序，因此 if 语句的数量始终

Q = 1 + 2 + 3 + ... + n-1  = n * (n-1) / 2

不是 Wiki code 检查

   ....    
   until not swapped

并可能在最佳情况下执行 (n-1) if 语句（排序数组）

Answer 2

if 语句将始终执行完全相同的次数，大致为 n^2 / 2。

语句 4 将多久执行一次，这是一个有趣的问题。特别是对于平均数，数学会很有趣。

指定 if 语句执行多少次【冒泡排序算法】

Specify how many times if statement will be done [bubble sort algorithm]

algorithm

sorting