问题描述
我编写了这个算法来使用冒泡排序对列表进行排序.这是对列表进行排序的最有效方法吗?
如果不是，为什么?
是什么降低了它的效率?有哪些替代方案?
I have written this algorithm to sort a list using bubble sort. Is this the most efficient way to sort a list?
If not, why?
What makes it less efficient and what are the alternatives present?
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])
谢谢！
推荐答案
在你上面的算法中，如果你的数组的length是5，它会执行内部if 语句 25 次.一般来说，当你有一个 n 大小的列表时，它肯定会做 n^2 操作，不包括 for 循环 和 交换.
In your above algorithm, if the length of your array is 5, it will execute the inner if statement 25 times. In general when you will have a list of n size, it will for sure do n^2 operations excluding the for loop and swapping.
对于10^6 大小的列表，它至少是10^12 个操作.C 或 C++ 每秒执行大约 10^9 次操作.所以你的这段代码需要 10^3 秒，也就是超过半小时.所以这是非常低效的.
For a list of size 10^6, it will be 10^12 operations atleast. C or C++ do around 10^9 operations per second. So this code of yours will take 10^3 seconds which is more than half an hour. So that's very much inefficient.
您可以使用更好的排序算法来代替冒泡排序，因为它们比这更快.
There are better sorting algorithms which you can use instead of bubble sort as they are faster than this.
还有很多其他技术，但这些是最常用的.
A lot of other techniques are also there but these are most common used.
除此之外，您不需要实现这些算法，因为从 C 到 Rust.如果需要，您可以使用该实现，甚至可以传递您自己的 comparator 函数.
Apart from that, you don't need to implement these algorithms as one of the most efficient one is already implemented in standard library of mostly each language from C to Rust. You can just use that implementation and even pass you own comparator function if you want.
这篇关于排序算法比冒泡排序更高效的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！