1

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

第一个例子：

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);

维基百科示例

输入：5 1 4 2 8

第一个例子：6 个比较

第二个例子：12 个比较

第一关：

( 5 1 4 2 8 ) --> ( 1 5 4 2 8 )，从 5 > 1 开始交换

( 1 5 4 2 8 ) --> ( 1 4 5 2 8 )，从 5 > 4 开始交换

( 1 4 5 2 8 ) --> ( 1 4 2 5 8 )，从 5 > 2 开始交换

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

第二关：

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

( 1 4 2 5 8 ) --> ( 1 2 4 5 8 ), Swap since 4 > 2 <-- 示例 1 到此为止

(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)

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

( 1 2 4 5 8 ) --> ( 1 2 4 5 8 ) <-- 示例 2 到此为止

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

4

6 回答 6

2

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

具体来说，对“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，最后一个比较将输入 [1] > input[2] -> input[3] 从不比较。

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

于 2012-11-29T17:33:47.403 回答
1

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

我确信他们都是对的。唯一的区别是您的第二个代码必须最后一次遍历已排序的数组。

于 2012-11-29T17:13:45.317 回答
1

两者都是对的。

第一个相对更有效。

于 2012-11-29T17:14:32.717 回答
1

不用想太多，看起来都对，但第一个似乎做的冗余操作较少，因此执行时间较短

第一个似乎取决于你最后一个 i 块是正确的事实，因此它甚至不会打扰它们。

于 2012-11-29T17:15:13.157 回答
1

在冒泡排序中，在第一次通过后，可以保证最大值将占据数组中的最后一个位置。这是因为根据定义，冒泡排序将最高值交换到数组的末尾。

这意味着在第二遍时，您不需要再次比较最后一个值，因为它保证大于或等于下一个较低索引中的元素。同样，在第 2 步之后，前两个元素将是最高值，并且彼此相对排序。

通过扩展，i通过后，i顶部元素将处于正确位置。

i第一个示例通过从最大j迭代器值中减去这一点来考虑这一点。第二个示例不必要地比较后续遍历中的上部元素。它没有伤害，但它是多余的，即未优化。它仍然是冒泡排序，因为它交换相邻的值，将较高值的元素移向数组的末尾。

那有意义吗？

于 2012-11-29T17:23:15.553 回答
1

第一个是所谓的优化冒泡排序

http://en.wikipedia.org/wiki/Bubble_sort#Optimizing_bubble_sort

第二个是“经典”冒泡排序。

于 2012-11-29T17:23:53.560 回答