首页 > 代码库 > 算法题——归并排序的原地实现

算法题——归并排序的原地实现

普通的归并排序,需要一个额外的数组来保存每次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了。参考:原地归并排序。

 

代码:(以后补上,思路最重要)