八大排序 (下)
@TOC
一、快速排序
1.挖坑法
1.过程
1.为了使用方便我们默认第一个数为 key,key 的值可以看作单独提出来了,key 所在的(pivot)坑的位置先从右边开始找比 key 小的数,找到后将值传给 pivot 所在位置,同时 pivot 指向右边
2.再从左边找比 key 大的数,找到后将值传给左边 pivot 所在位置 ,同时 pivot 指向左边
3.当 begin 与 end 指向同一个位置时,则将关键字传入进去 ,循环结束
2.对于递归结束条件的分析
当递归到最后时,发现只剩下一个数或者没有数存在,而在循环中成立的条件为 lelft<right 当 left==right 时,只有一个数当 left>right 时,没有数存在
3. 代码实现
4.快速排序的时间复杂度
理想情况下,每次都用坑 pivot 将 left 与 right 区间平分 即满二叉树
每一层都会将所有数遍历一遍,所有每一层的时间复杂度为 O(N)一共遍历了高度次 根据二叉树性质:2^h-1=N h=log N
快速排序的整体时间复杂度为 O(N*logN)
5.三数取中
快排什么时候为最坏情况有序时最坏以顺序为列 ,每次只能选出一个数 此时的时间复杂度为 O(N^2)
所以为了防止这种情况的发生,采用三数取中
6.小区间优化
使用小区间优化是为了减少函数调用的次数
当我们递归会发现最后几层的函数调用占据了绝大多数我们假设当一个区间内相差不超过 10,就消除消除的部分则使用直接插入排序直接插入排序在这里:八大排序(上)
2.左右指针法
1.过程
简单来说,就是先从右面找比关键字小的 ,再从左边找比关键字大的 ,两者交换,当 left==right 时,将此时的值与关键字交换
2.代码实现
3.前后指针法
1.过程
1.当 cur 的值比 key 大时,cur++
2.当 cur 的值比 key 小时 ,prev++ ,并交换两者的值
3.当 cur 遍历完数组时,就将 prev 位置的值与 key 位置的值交换
2.代码实现
4.非递归
非递归借助了数据结构栈的模拟:栈和队列的实现
1.过程
栈有先进后出的原则 ,所以我们先判断下是否符合区间值>1 的条件,如果符合,则先将右边的右入栈,再入右边的左 ,其次入左边的右,再入,做左边的左呈现出来则为 ,左边的左 ,右 ,右边的左,右
2.代码实现
二、归并排序
1.递归
1.过程
通过递归的方式使左半区间与右半区间有序 ,最后使整体区间有序
2.代码实现
3.归并排序的时间复杂度
每次都分为 两个对半的区间可以看作是一个满二叉树 2^h-1=N h=log N 当向上递归排序时,每一层的区间排序会遍历到所有数 n 时间复杂度为 O(N)即归并排序整体时间复杂度为 O(N*log N)
4.递归的缺陷
如果栈深度太深,栈的空间不够用,可能会造成溢出
2.非递归
1.过程
采用循环,从之前的底层开始进行,一直 到整体有序 结束假设此时数组中有 8 个数通过 [i ,i+gap-1] [i+gap , i+2*gap-1] 每次都分为两个区间则 gap 为 1 时就将 左边区间个数为 1 与右边区间个数为 1 进行排序 gap 为 2 时就将 左边区间个数为 2 与右边区间个数为 2 进行排序 gap 为 4 时就将 左边区间个数为 4 与右边区间个数为 4 进行排序
2.代码实现
3.注意事项
左区间存在,右区间不存在时,左区间不需要归并
当将左区间的 4 个数 ,与右区间进行归并时发现右区间只有三个数,第 4 个数不存在,所以修正回第三个数作为 end2
当左区间的数不够 gap 所分的数,右区间不存在时,若将左区间拷贝回去会出现随机值所以进行归并的才拷贝回去,没有进行的就不需要拷贝 ,所以将返回过程放入循环中
三、计数排序
1.思想
1.统计数,与其下标的大小对应,观察每个下标所对应的数量,直接输出就排好序了 ,此时为绝对映射位置
2.若数字过大 ,前面的空间就会浪费掉,所以避免这种情况的发生,则进行相对位置的映射
2.代码实现
时间复杂度为 O(N)
版权声明: 本文为 InfoQ 作者【lovevivi】的原创文章。
原文链接:【http://xie.infoq.cn/article/0064fbb95481c8ba517a68a7d】。文章转载请联系作者。
评论