Question

排序算法的比较次数跟数据的多少无关

Answer 1

跟数据的优化方法有关。

冒泡排序有一种优化方法，就是在每趟冒泡的时候都检测这次是否有交换元素的顺序，如果没有交换就说明序列是排好序的，下次就不用再冒泡了，所以和初始序列是有关系的。冒泡排序是将序列中值大的压到序列顶端，就像冒泡一样一个一个的将值大的冒出来。

假设n个值，一趟排序后会将最大的排到位置n，对前n-1位进行第二趟排序，直至某一次排序中序列中的值是递增的，排序结束。所以说有序情况和无序情况尽管每一趟关键字比较次数相同，但有序情况下排序趟数要少，所以总比较次数也要小。

算法稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。