上面是一篇非常好的总结,我下面主要说的是对于其中一些算法的补充。
1、归并排序
归并排序分为两步,划分与合并
在划分完成后,在合并过程中构建有序,让合并两方最头(该部分最小)比较,后再添加回原数组。
2、堆排序
可以参照于优先级队列的实现方式,构建完全二叉树,实现。可以用Vector向量实现,逻辑上是树,但物理上是数组,已知节点秩为R,则其父节点为R/2,其左右孩子为R2+1,(R+1)2
维护堆的两种动态操作:
- 插入时上滤:插入到尾部时,若比父节点大,则上移。
- 删除时下滤:删除最大节点后,用末位的点已到根节点,与父节点比对,大者孩子互换,下移
当然这里只用到上滤就够了,每次插入一个节点,假设最坏情况需要上滤到根节点,即共logn层,则有n*logn次,即可得到复杂度
o(nlogn)
3、快速排序变种
这里补充的是快排的优化,快排的优化点就是减少数据的交换次数。将数据分为4部分,如下图
p为轴点,L为小于p部分,G为大于p部分,U为未比较部分,x为当前比较的那个数。步骤为
- 比较x与p大小,若大于p,则不进行任何操作(因为x和G相接壤,G会变大,U变小)。若小于p,则将G的第一个节点(或者mi+1)与x交换(L变大,U变小)
- 直至U为0,将p与mi互换(和快排一样)
- 分治递归重复步骤1、2直至完成排序
4、锦标赛排序(树排序)
将所有待排序数字作为树的叶子节点,兄弟节点比较,大的成为各种的父节点,依次重复直至到根节点。