当前位置: 代码迷 >> 综合 >> 原地归并算法
  详细解决方案

原地归并算法

热度:33   发布时间:2024-01-16 01:32:13.0

 

 

断更一个月,发现自己再学习上有点懒惰了...

最近在啃《算法(第4版)》,进度有点慢,索性做点读书笔记

 

 

书中抽象算法

public static void merge(Comparable[] a, int lo, int mid, int hi)
{   // 将 a[lo..mid] 与 a[mid+1..hi] 归并int i = lo, j = mid+1;for (int k = lo; k <= hi; k++)    // 将 a[lo..hi] 复制到 aux[lo..hi]aux[k] = a[k];for (int k = lo; k <=hi; k++)if (i > mid)                    a[k] = aux[j++];else if (j > hi)                a[k] = aux[i++];else if (less(aux[j], aux[i]))  a[k] = aux[j++];else                            a[k] = aux[i++];
}

 

思考

 

该方法思路概括为:

左半用尽取右

右办用尽取左

左右均有取小

但是这么做好像不全面

当左半/右半用尽后, 并没有判断大小的操作

不知道在后面会不会填坑

====== 10分钟后更新 ======

别填坑了, 归并前左右子数组会先排序?

果然写下来有助于自己思考

======

  相关解决方案