排序算法比冒泡排序更有效

Question

我编写了这个算法来使用冒泡排序对列表进行排序。这是排序列表的最有效方法吗？
如果不是，为什么？
是什么导致它效率低下，目前有哪些替代方案？

def BubbleSort(List):
     for i in range(len(List)-1):
          for Number in range(len(List)-1):
               if List[Number] > List[Number+1]:
                    List[Number], List[Number+1] = List[Number+1], List[Number]

print(BubbleSort([5,2,1,4,3])

谢谢！

Answer 1

在你上面的算法中，如果你的数组的length是5，它会执行内部的if statement 25次。一般来说，当你有一个 n 大小的列表时，它肯定会执行 n^2 操作，不包括 for loop 和 swapping.

对于大小为 10^6 的列表，至少需要 10^12 次操作。 C 或 C++ 每秒执行大约 10^9 次操作。所以你这段代码需要 10^3 秒，也就是半个多小时。所以这是非常低效的。

您可以使用更好的排序算法来代替 bubble sort，因为它们比这更快。

还有很多其他技术，但这些是最常用的。

除此之外，您不需要实现这些算法，因为最有效的算法之一已经在从 C 到 Rust 的大多数语言的标准库中实现。您可以只使用该实现，如果需要，甚至可以传递您自己的 comparator 函数。

排序算法比冒泡排序更有效

Sorting algorithms more efficient than bubble sort

python

algorithm

programming-languages