冒泡排序:它是冒泡排序的改良(一次下沉再一次上浮),最优情况和最坏情况与冒泡排序差不多,但是一般情况下它要好过冒泡排序,它一次下沉,再一次上浮,这样避免了因一个数的逆序,而造成巨大的比较。如(2,3,4,…,n-1,n,1),用冒泡排序需要n(n-1)/2次比较,而此排序只要3轮,共比较(n-1)+(n-2)+(n-3)次,第一轮1将上移一位,第二轮1将移到首位,第三轮将发现无数据交换,序列有序而结束。但它同样是一个对数据有序性非常敏感的排序算法,只适合于数据基本有序的排序。
直接选择排序:简单的选择排序,它的比较次数一定:n(n-1)/2。也因此无论在序列何种情况下,它都不会有优秀的表现(从上100K的正序和反序数据可以发现它耗时相差不多,相差的只是数据移动时间),可见对数据的有序性不敏感。它虽然比较次数多,但它的数据交换量却很少。所以我们将发现它在一般情况下将快于冒泡排序。 |