冒泡排序与选择排序的效率
Efficiency of Bubble vs. Selection Sort
我知道冒泡排序和选择排序的大 O 值是相同的，(n)^2，但是当我尝试 运行 两者都使用大小为 1000 的数组时，冒泡排序需要962037次交换对数组进行排序，而选择排序只需要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），这两个数字仍然可以相差一个任意大的值。
Big O 表示法提供了无症状成本，但是，省略了所有附加值和常量。此外，对于小数字的实际比较，您需要查看平均比较次数。更具体地说，冒泡排序平均每个条目需要 n/4 个交换，而选择排序只需要 1 个，请参阅此 post 了解更多详细信息。比较的次数也将取决于初始分布，例如数据是半排序的还是完全随机的。
我知道冒泡排序和选择排序的大 O 值是相同的，(n)^2，但是当我尝试 运行 两者都使用大小为 1000 的数组时，冒泡排序需要962037次交换对数组进行排序，而选择排序只需要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），这两个数字仍然可以相差一个任意大的值。
Big O 表示法提供了无症状成本，但是，省略了所有附加值和常量。此外，对于小数字的实际比较，您需要查看平均比较次数。更具体地说，冒泡排序平均每个条目需要 n/4 个交换，而选择排序只需要 1 个，请参阅此 post 了解更多详细信息。比较的次数也将取决于初始分布，例如数据是半排序的还是完全随机的。