Question

元素比较次数与元素初始排列无关是哪种排列法

Answer 1

冒泡排序：最好情况需比较n-1次，最坏情况需比较n（n-1）/2；

选择排序：最好情况需比较n（n-1）/2，最坏情况需比较n（n-1）/2；

对分排序：最好情况需比较n/2logn，最坏情况需比较近似nlogn；

根据算法本身,通过计算迭代次数,或建立递推方程求解。

归并排序的比较次数介于(nlogn)/2和(nlogn)-n+1。

如果以大O表示法的话，O((nlogn)/2)=O((nlogn)-n+1)=O(nlogn)。因此，正如chiconysun所说，最好和最坏相差接近2倍，但是最好、最坏和平均的时间复杂度都是O(nlogn) 。

扩展资料：

选择排序法的第一层循环从起始元素开始选到倒数第二个元素，主要是在每次进入的第二层循环之前，将外层循环的下标赋值给临时变量，接下来的第二层循环中，如果发现有比这个最小位置处的元素更小的元素，则将那个更小的元素的下标赋给临时变量，最后，在二层循环退出后，如果临时变量改变，则说明，有比当前外层循环位置更小的元素，需要将这两个元素交换。

参考资料来源：百度百科-选择排序法

Answer 2

楼上的不准确，虽然时间复杂度一致，但是元素的比较次数最好和最坏相差接近2倍：
假设递增排序，如果两个都是n个元素的有序序列合并，最少比较次数为n，此时是一个序列所有元素都比另外的第一个元素小，但是最多比较次数是2n-1，正好是两者的完全交错

Answer 3

冒泡排序
：最好情况需比较n-1次，最坏情况需比较n（n-1）/2；
选择排序
：最好情况需比较n（n-1）/2，最坏情况需比较n（n-1）/2；
对分排序：最好情况需比较n/2logn，最坏情况需比较近似nlogn；
根据算法本身，通过计算迭代次数，或建立
递推
方程求解