【Java】归并排序的非递归实现

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

归并排序可以采用递归方法（见：归并排序），但递归方法会消耗深度位O(longn)的栈空间，使用归并排序时，应该尽量使用非递归方法。本文实现了java版的非递归归并排序。

更多：数据结构与算法合集

思路分析

递归排序的核心是merge(int[] arr, int start, int mid, int end)函数，讲[start~mid-1]和[mid~end]部分的数据合并，递归代码是使用递归得到mid，一步步分解数组。

非递归时，我们直接定义要合并的小数组长度从1开始，在较小的长度数组都合并完成后，令长度*2，继续进行合并，直到合并完成。

完整Java代码

（含测试代码）

public class MergeSort2 {
public void mergeSort(int[] arr) {
if(arr==null || arr.length<=0)
return;
int width = 1;
while(width<arr.length) {
mergePass(arr,width);
width*=2;
}
}private void mergePass(int[] arr,int width) {
int start=0;
while(start+2*width-1<arr.length) {
int mid=start+width-1;
int end=start+2*width-1;
merge(arr,start,mid,end);
start=start+2*width;
}
//剩余无法构成完整的两组也要进行处理
if(start+width-1<arr.length)
merge(arr, start, start+width-1, arr.length-1);
}private void merge(int[] arr, int start, int mid, int end) {
int i=start;
int j=mid+1;
int[] temp = new int[end-start+1];
int index=0;
while(i<=mid && j<=end) {
if(arr[i]<=arr[j])
temp[index++]=arr[i++];
else
temp[index++]=arr[j++];
}
while(i<=mid)
temp[index++]=arr[i++];
while(j<=end)
temp[index++]=arr[j++];for(int k=start;k<=end;k++)
arr[k]=temp[k-start];
}//==========测试代码=================
public void test1() {
int[] a = null;
mergeSort(a);
System.out.println(Arrays.toString(a));
}public void test2() {
int[] a = {};
mergeSort(a);
System.out.println(Arrays.toString(a));
}public void test3() {
int[] a = { 1 };
mergeSort(a);
System.out.println(Arrays.toString(a));
}public void test4() {
int[] a = { 3, 3, 3, 3, 3 };
mergeSort(a);
System.out.println(Arrays.toString(a));
}public void test5() {
int[] a = { -3, 6, 3, 1, 3, 7, 5, 6, 2 };
mergeSort(a);
System.out.println(Arrays.toString(a));
}public static void main(String[] args) {
MergeSort2 demo =new MergeSort2();
demo.test1();
demo.test2();
demo.test3();
demo.test4();
demo.test5();
}
}