交换的冒泡排序数
交换的冒泡排序数
提问于 2013-11-18 04:06:31
要使用冒泡排序算法对包含6个元素{11,5,7,3,2,1}的列表进行排序，您可以手动查找具有14个交换的元素。我知道下面的公式给出了比较
n(n-1)/26(6-1)/2 = 15。为什么是15而不是14？
另外，快速排序和插入排序是否有类似的公式？
提前感谢！
回答 2
Stack Overflow用户
回答已采纳
发布于 2013-11-18 04:15:16
交换并不等同于比较。对于该列表，无论元素的顺序如何，都会有15次比较。交换的数量取决于元素的实际顺序。在插入排序中，比较次数与冒泡排序相同。对于qsort，这可能会有帮助：https://math.stackexchange.com/questions/397100/compute-number-of-comparisons-in-quicksort-pivoting-on-median-or-third
Stack Overflow用户
发布于 2020-12-03 11:05:30
按升序排列：
在冒泡排序中，最大的元素向右移动。因此，当在右侧发现较小的元素时，交换就完成了。
因此，要计算一个元素的交换次数，只需计算右侧小于它的元素的数量。
数组{11，5，7，3，2，1}
对于11，右侧较小的元素数: 5(5,7,3,2,1)
对于5: 3(3,2,1)
对于7: 3(3,2,1)
对于3: 2(2,1)
对于2: 1(1)
对于1: 0
交换总额: 5+3+3+2+1 = 14
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20035505
复制相关文章
相似问题
腾讯云开发者
