的情况,所以如果两个元素相等,他们不会交换;所以,相等元素的前后顺序没有改变,从
原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。
(4)快速排序
快速排序有两个方向,左边的i下标一直往右走,当a[i] <= [center_index](center_index中
枢元素的数组下标),一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] >
a[center_index]。如果i和j都走不动了,i <= j, 交换a[i]和a[j],重复上面的过程,直到i>j。
交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把
前面的元素的稳定性打乱,比如序列为 5,3,3,4,3,8,9,10,11, 现在中枢元素5和3(第5个元
素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序
算法,不稳定发生在中枢元素和a[j]交换的时刻。
快速排序是高效排序算法了。实践证明,快速排序是所有排序算法中最高效的一种。它
采用了分治的思想:先保证列表的前半部分都小于后半部分,然后分别对前半部分和后半部
分排序,这样整个列表就有序了。这是一种先进的思想,也是它高效的原因。因为在排序算
法中,算法的高效与否与列表中数字间的比较次数有直接的关系,而"保证列表的前半部分
都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较
了,大大减少了数字间不必要的比较。但查找数据得另当别论了。
(5)归并排序
所谓“归并”,试讲两个或两个以上的有序文件合并成一个新的有序文件。归并排序是把一
个有n个记录的无序文件看成是由n个长度为1的有序子文件组成的文件,然后进行两两归
并,得到[n/2]个长度为2或1的有序文件,再两两归并,如此重复,直至最后形成包含n
个记录的有序文件为止。所以,归并排序也是稳定的排序算法。
(6)基数排序
基数排序的思想是按组成关键字的各个数位的值进行排序,他是分配排序的一种。基数
排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。
有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就
是高优先级高的在前,高优先级相同的低优先级高的在前。为了减少记录的移动次数,队列
可以采用链式存储分配,称为链队列。基数排序基于分别排序,分别收集,所以其是稳定的
排序算法。
(7)希尔排序(shell)
希尔排序又称为“缩小增量排序”是按照不同步长对元素进行插入排序,当刚开始元素很无
序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长
很小,插入排序对于有序的序列效率很高。关键步骤是取增量d,那全体记录分成d组,进
行直接插入排序,直到d=1.所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入
排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排
序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell
排序是不稳定的。
(8)堆排序
我们知道堆的结构是节点i的孩子为2*i和2*i+1节点,大顶堆要求父节点大于等于其2
个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列,堆排序的过程
是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的
选择当然不会破坏稳定性。但当为n /2-1, n/2-2, ...1这些个父节点选择元素时,就会破坏稳
定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面
一个相同的元素没有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序
不是稳定的排序算法
发表评论