我知道冒泡排序和选择排序的大 O 值是相同的 (n)^2，但是当我尝试使用大小为 1000 的数组运行两者时，冒泡排序需要 962037 次交换来对数组进行排序，而选择排序Sort 只需要 988 次交换即可对数组进行排序。为什么这些不同？
因为复杂度是指比较的次数，而不是交换的次数。两者都需要O(n^2)次比较，但选择排序只需要n-1最坏情况下的交换 (O(n))，而冒泡排序可能需要最多n*(n-1)/2交换 (O (n^2))。
即使复杂性指的是交换次数 - 因为符号忽略了常量（实际上可能是1000*n^2 + 500*n*log(n) + 100*n + 10，而另一个可能是n^2），两个数字仍然可能相差任意大的值。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
