c# - 两种冒泡排序算法的区别

Question

我找到了两种气泡算法，但我不确定哪一种是正确的...

第一个例子:

for (int i = 1; i < input.Length-1; i++)
    for (int j = 0; j < input.Length - 1 - i; j++)
        if (input[j] > input[j + 1])
            swap(input, j, j + 1);

第二个例子:

for (int i = 1; i < input.Length-1; i++)
    for (int j = 0; j < input.Length - 1; j++)
        if (input[j] > input[j + 1])
            swap(input, j, j + 1);

Wikipedia Example

对于输入:5 1 4 2 8

第一个例子:6个比较

第二个例子:12次比较

First Pass:

( 5 1 4 2 8 ) --> ( 1 5 4 2 8 ), Swap since 5 > 1

( 1 5 4 2 8 ) --> ( 1 4 5 2 8 ), Swap since 5 > 4

( 1 4 5 2 8 ) --> ( 1 4 2 5 8 ), Swap since 5 > 2

( 1 4 2 5 8 ) --> ( 1 4 2 5 8 )

Second Pass:

( 1 4 2 5 8 ) --> ( 1 4 2 5 8 )

( 1 4 2 5 8 ) --> ( 1 2 4 5 8 ), Swap since 4 > 2 <-- Example 1 stop here

( 1 2 4 5 8 ) --> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) --> ( 1 2 4 5 8 )

Third Pass

( 1 2 4 5 8 ) --> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) --> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) --> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) --> ( 1 2 4 5 8 ) <-- Example 2 stop here

编辑:当我说哪个是正确的时，我的意思是哪个是原始的冒泡排序

Answer 1

第一个算法不正确。 如果数组中的最后一个元素不是最大的，它将失败。

具体来说，对“j”的迭代:

for (int j = 0; j < input.Length - 1 - i; j++)

似乎跳过了最后一个元素。 如果您的输入是 {0, 2, 2, 1} 然后你的 input.Length = 4

上面的 for 循环将有条件 j < 4 - 1 - i，其中 i = 1 所以 j < 4 - 1 - 1，所以 j < 2 所以最后使用的 j 将是 j = 1，最后比较将是 input[1] > input[2] -> input[3] 永远不会被比较。

您可以通过将 for 循环更改为 j <= input.Length - 1 - i 来修复它