归并排序,有递归实现与迭代实现两种方式,这里给出递归实现的方案。
归并排序的含义是把两个有序的序列合并成一个有序的序列。
具体做法更简单:(这里假设两个有序序列均是从小到大排列的)
- 首先是创建一个空序列,长度为 这两个序列的长度之和;
- 然后是从前向后遍历这两个序列的值,取出每次比较的较小值存放进这个新序列中,然后一直往后更新索引值,直到其中一个序列的全部元素放入到新序列中;
- 然后把另一个序列中剩余的值,直接全部添加到这个新的序列的末尾
经过上面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,3
,2
会继续分成1,1
3
分成1, 2
,2
会继续分成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]
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)