首页 > 代码库 > 算法题——归并排序的原地实现
算法题——归并排序的原地实现
普通的归并排序,需要一个额外的数组来保存每次merge的结果;如果要求不使用额外空间,那么每次merge的时候需要做一些处理。
思路:
- 合并left[] 和 right[]时,假如right[0]应该放入left[3],那么:①可以用一个var来保存right[0],然后将left[3]之后的元素右移一次,再将var值放入left[3];②也可以交换right[0]和left[3]的值,然后left[0]在新的位置向后遍历,找到合适的位置,再把前面的移位。 寻找合适位置的过程是一次插入排序,复杂度就是O(N2 * lgN)了。
- 另一个思路是,合并时,right数组向右找到第一个大于left当前元素的值,然后以块为单位交换。这个过程就类似于i am a student 转换为student a am i了。参考:原地归并排序。
代码:(以后补上,思路最重要)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。