排序算法实战高级
Contents
手写一套经典的所有排序算法源码
https://github.com/huangzhenshi/ClassicSort/tree/master
游标因子的设置
- 选择排序需要一个游标,int index=0,标志该轮比较当中,最大值所在的下标位置
- 插入排序需要一个游标,int index=j,如果后面元素比前面元素小,则交换之后游标向前游动
- 希尔排序需要一个游标,类似于插入排序,只是游标左游的长度为d
- 快速排序需要两个游标,除了 low high这种原始标志位,还需要head标识前置哨兵目前所在的位置和tail标识数组后置哨兵所在的位置(last哨兵后面的都比arr[index]大)
- 堆排序需要一个游标,来标志末位元素的位置
- 归并排序需要三个游标,除了 low mid high ,还需要 i j k,来实现比较拷贝
排序原理
- 选择:遍历比较数组最大值,通过游标标记,最后和末位交换。2个for循环和index解决问题。
- 冒泡:遍历比较最大值,不停交换最大值一直到末位,2个for循环解决问题。
- 插入:维护一个递增的数组,通过一个游标,和最大的数比,比最大的大就break;否则游标和比较对象都左移
希尔:3层for循环+while,插入排序的改进版本,跨度插入排序形成基本有序数组再插入排
快排:每次首位元素通过交换找到它在该数组段中的位置,再递归,引入low high head tail关键标记位。基于这种思路,可以解决无序数组中中位数,和无需数组求中位数的算法,随机第一个元素切分数组,缩小范围的方式来定位查找目标。
归并(分治):精华是拆分问题,把数组拆分成2个小数组最后在递归性的从小问题解决到最大的问题,第二个核心在于2个连续的有序数组的merge方法。利用一个辅助数组。
复杂度
空间复杂度:
- 一般的排序都是平均的空间复杂度都是O(1),只需要支付 exchange(int start,int end,int[] arr)时的成本,最佳就是本来有序O(0)
- 归并排序依赖一个辅助的数据,空间复杂度为 O(N)
- 快排的依赖是递归,O(logN)
时间复杂度
- 快排
- 最佳的时间复杂度 NlogN,最差 N平方,平均NlogN
- 最佳是每次都是中位,递归长度减半,logN次均分,最差是数组正序或者逆序
- 解决最差情况:哨兵排之前做一次随机取值,再交换的处理。
- 改进方法2:N<47时用插入,提速
算法实现的注意事项
- 选择、冒泡、插入两个for循环,所以时间复杂度为N平方
- 希尔排序:4层for循环2个因素基本上
- 快排:递归套一层while循环判断tail和head是否碰头
插入排序代码实现
- 两层for循环(或者一个for循环+while)
- 需要一个关键游标 index,每次左移的时候,比较对象也要一起移动
- 比较大小的时候,大于则break;小于则交换且游标和比较对象一起左移
希尔排序代码实现
- 四层for循环,2层用于快排、1层用于i=0 i
0 - 需要两个关键游标 d和index
快排的代码实现
- 一个locate,一个while
- 2个游标:head、tail;2个判断 high<=low return,while(tail>head)
堆排序的代码实现
- 写MaxPQ,size,sink(),swim()
- 构建有序堆(N/2开始依次sink())
- for循环,交换末位,setSize(–tail),sink(1)
归并排序的代码实现
- 拆分问题,start<end时,求mid,拆分2个问题,merge
- 归并方法:3个游标、一个辅助数据、3层while一层for,写入又写会arr1数组当中
优先队列
- 解决的问题:构建一个有序堆,堆顶的元素最大,且重新插入一个元素,或者删除堆顶元素,堆重构的代价并不大。用于堆排序,或者查找最值的业务场景中
- N指的是list.size()-1,数组首位为null
- swim() ,有序堆从末位追加一个元素,调用swim()方法,重建堆有序,用于已经堆有序的堆中添加新元素
- 构建优先队列的时候要控制size,因为最后排序的时候涉及到堆顶和数组末位交换位置实现排序功能
- sink()的时候首先要判断是否有2个子节点,然后取最大的一个和父节点比较,不然会出错
代码
选择排序
|
插入排序
|
Shell
|
Quick
|
heap
|
Merge
|