2

根据Tenenbaum 的使用 C的数据结构，冒泡排序的改进之一是让连续通过以相反的方向进行，以便小元素快速移动到前面，这将减少所需的通过次数 [pg 336]。我设计了两个例子，一个支持这个说法，另一个反对这个说法。

Supports: 25 48 37 12 57 86 33 92
iterations using usual Bubble sort :
    25 48 37 12 57 86 33 92
    25 37 12 48 57 33 86 92
    25 12 37 48 33 57 86 92
    12 25 37 33 48 57 86 92
    12 25 33 37 48 57 86 92

iterations using improvement:
    25 48 37 12 57 86 33 92
    25 37 12 48 57 33 86 92
    12 25 37 33 48 57 86 92
    12 25 33 37 48 57 86 92

against: 3 4 1 2 5
iterations using usual Bubble sort:
    3 4 1 2 5
    3 1 2 4 5
    1 2 3 4 5

iterations using improvement:
    3 4 1 2 5
    3 1 2 4 5
    1 3 2 4 5
    1 2 3 4 5

那么这种改进总是有帮助的说法是错误的吗？或者我在这里做错了什么？

4

1 回答 1

0

您在上面给出的示例表明，该算法并不是对标准冒泡排序的严格改进。

这种方法（有时称为“鸡尾酒排序”）的优点是，在数组末尾有很多小元素的情况下，与普通冒泡排序相比，它会迅速将它们拉到前面。例如，考虑这个数组：

2 3 4 5 6 7 8 9 10 11 12 ... 10,000,000 1

使用正常的冒泡排序，需要 9,999,999 次遍历该数组才能对其进行排序，因为元素 1，这是不合适的，每次迭代只会向前交换一步。另一方面，对于鸡尾酒排序，这将只需要两次传递——一次初始传递，然后是反向传递。

虽然上面的例子肯定是人为的，但在一个随机打乱的数组中，可能会有一些更小的元素接近数组的末尾，并且冒泡排序的通过次数必须很大才能将它们移回。双向推进有助于加快这一进程。

也就是说，冒泡排序是一个非常糟糕的排序算法选择，所以希望这只是一个理论上的讨论。:-)

于 2015-08-27T20:30:41.287 回答