我想知道冒泡排序最好的情况是什么?例如,可能存在这样一种情况,其中可能没有对所说的最后2次传递的交换。我正在用C语言编写我的程序。假设我有一个由5个元素组成的数组,我给出的元素是1,2,5,4,3,那么在最后的2次传递中不会有任何变化?
发布于 2009-08-31 17:14:35
最好的情况是一次通过。列表应该已经被排序了。
无交换=完成。
发布于 2009-12-27 16:49:58
最好的情况:最好的情况是列表已经排序。a)会有比较,但没有交换,执行时间在O(n2) b),但如果我们跟踪每一遍中的交换,并终止程序,检查是否没有交换。那么程序将只需要一次传递和最大值。在单遍中需要(n-1)个比较,我们可以说复杂度是O(n)的数量级。
发布于 2009-08-31 17:15:28
请参阅Bubble sort
冒泡排序的最坏情况和平均复杂度都是О(n²),其中n是要排序的项数。存在许多排序算法,它们的最坏情况或平均复杂度为O( n )。甚至其他О(n²)排序算法,如插入排序,往往比冒泡排序具有更好的性能。因此,当n较大时,冒泡排序并不是一种实用的排序算法。
https://stackoverflow.com/questions/1358383
复制相似问题