1

据我了解，冒泡排序（低效版本）将执行以下操作：

2 3 8 6 23 14 16 1 123 90  (10 elements)
  1. 比较元素[0]和元素[1]
  2. 如果[0]大于[1]，则交换完成。
  3. 如果[1]大于[0]，则没有完成交换。

然后冒泡排序将继续比较元素[1]等等[2]，总共创建 9 次交换。

但是，有没有办法保证在第一次通过时，最高的数字将在适当的位置[9]，而在第二次通过时，两个最高的数字将在适当的位置[7]和[8]？

4

4 回答 4

3

不要使用冒泡排序。考虑高级算法，例如

遇到一个问题如何优化冒泡排序我的答案是优化它，只要它还不是 Timsort。

于 2011-11-29T06:25:54.973 回答
3

冒泡排序是一种特定的算法——询问它是否可以优化以获得你想要的属性是没有意义的。它还具有 O(n^2) 复杂度，这就是它很少使用的原因。

还有其他排序算法，比如选择排序，它的属性更接近你想要的。选择排序将保证在第 i 次通过时，最小的 i 个元素位于正确的位置。但是，选择排序也是 O(n^2)，如果您预计对大量数据进行排序，则应避免选择排序。

像 Basile 和 Jan 一样，我建议学习一种更高效、更标准的排序算法，快速排序。快速排序应用非常广泛，在 C 标准库中可用。维基百科对算法的描述比较简洁；在 Google 上搜索也会提供许多动画版本的快速排序，这对学习算法很有帮助。

于 2011-11-29T06:42:16.397 回答
1

如果您正确地实现了冒泡排序算法，那么在第一遍结束时，最高数字必须始终位于正确的位置。

优化只是在第二遍结束时少走一步：

let n equal top_element - 1
while n is greater than or equal to zero
  for i = 0 to n
    if element i is greater than element i+1 then swap
  subtract 1 from n
于 2011-11-29T11:12:12.353 回答
0

可以做两件事来优化冒泡排序。首先，跟踪单次通过期间是否发生任何交换。如果没有发生，那么该列表必须已经完全排序，因此您不必进行任何额外的传递。此外，每次通过都减小循环的范围，因为在每次通过后，应该再有一个元素位于正确的位置。

于 2017-11-29T04:49:04.443 回答