Java 归并排序

Java 归并排序,第1张

归并排序,有递归实现与迭代实现两种方式,这里给出递归实现的方案。

归并排序的含义是把两个有序的序列合并成一个有序的序列。

具体做法更简单:(这里假设两个有序序列均是从小到大排列的)

  1. 首先是创建一个空序列,长度为 这两个序列的长度之和;
  2. 然后是从前向后遍历这两个序列的值,取出每次比较的较小值存放进这个新序列中,然后一直往后更新索引值,直到其中一个序列的全部元素放入到新序列中;
  3. 然后把另一个序列中剩余的值,直接全部添加到这个新的序列的末尾

经过上面3步,就完成了归并排序。

而如果当前是一个无序的队列,怎么直接使用这个归并排序进行排序呢?
其实是不能直接使用归并排序直接排序的。

使用递归法可以间接利用归并排序完成对一个无序序列的排序 *** 作.

递归法的原理是分而治之。比如你的一个数组长度为9

  • 那么这时候先分割成两个数组,长度分别为4,5,这时候呢,这两个数组还是无序的;
  • 然后呢,又继续分,比如第一个长度为4的数组,继续分成两个 长度分别为2,2的数组。(长度为5的数组跟这个长度为4的数组的处理方式一样的,就不描述了)但是,这时候这两个2,2长度的数组还是无序的;
  • 继续分,把长度为2的数组分成长度为1,1的两个数组。注意,这时候,这两个数组其实就是有序的了。因为数组里面只有一个元素,那就是有序数组了。

分完了之后呢,就是归并的 *** 作了:

  • 首先是拿到两个长度为1,1的数组,进行归并,变成一个有序的,长度为2的数组了;(后面的也是一样,这时候会得到很多长度为2的有序数组)
  • 然后是把长度为2的有序数组进行归并,这时候能得到一个长度4的有序数组。(不止一个,可以同步进行,后面的部分就能得到一个长度为5的有序数组)
  • 然后把长度为4,5 的两个有序数组进行归并,得到了一个有序的,长度为9的数组了。
  • 【此时,利用归并排序对一个长度为9的无序数组的排序就完成了】

这里使用递归是进行的处理的,分到什么程度呢?就是分到两个无序数组的长度分别为1,1的时候,这时候我们认为这两个小数组是有序的,这时候就开始的 *** 作,这时候开始慢慢把这些小有序数组合并成有序大数组;

另外说一下上面的长度为5数组的分解后续:
5 分成 2,32 会继续分成 1,1
3 分成 1, 22 会继续分成 1,1
1 不会分成1, 0, 到上一步就结束的 *** 作了。
… 分割线…
的时候呢,这个由3 --> 1, 2 最后也是合成为 1,(1+2) -> 3

下面是具体实现:


    /**
     * 归并排序.
     * 
     *     归并 *** 作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的 *** 作。归并排序算法依赖归并 *** 作。
     * 
* * @param array origin array * @param left start index * @param right end index * @param cache to cache temp results. */
private static void merge(int[] array, int left, int right, int[] cache) { if (left >= right) { // 这时候 长度为`0`,直接出栈了,回到上一个调用栈,也就是长度为`1`的栈,这时候就会开始执行 // 后面的`合`的逻辑了。 return; } // int mid = left + (right - left) / 2; int mid = (left + right) / 2; merge(array, left, mid, cache); merge(array, mid + 1, right, cache); // left arr [left,mid]; right arr [mid+1, right] int pl = left; int pr = mid + 1; int pt = pl; while (pl <= mid && pr <= right) { if (array[pl] < array[pr]) { cache[pt++] = array[pl++]; } else { cache[pt++] = array[pr++]; } } // System.out.printf("pt=%d, pl=%d, pr=%d\n", pt, pl, pr); // if left not empty while (pl <= mid) { cache[pt++] = array[pl++]; } // if right not empty while (pr <= right) { cache[pt++] = array[pr++]; } // then copy to origin array // noinspection ManualArrayCopy for (int i = left; i <= right; ++i) { array[i] = cache[i]; } }

注意一下,上面的实现,只使用了一个临时数组 cache[array.length],但是,每次利用的不一定是一个完成的[0,length) 的长度,只是,很少的一部分。

下面是调用的部分:

 int[] origin = {2, 4, 6, 8, 1, 3, 5, 7, 9};
 System.out.println("before: "+ Arrays.toString(origin));
 merge(origin, 0, origin.length - 1, new int[origin.length]);
 System.out.println("after : "+ Arrays.toString(origin));

输出如下:

before: [2, 4, 6, 8, 1, 3, 5, 7, 9]
after : [1, 2, 3, 4, 5, 6, 7, 8, 9]

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/794232.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-06
下一篇 2022-05-06

发表评论

登录后才能评论

评论列表(0条)

保存