/**
* 2路归并排序的非递归实现
* 归并排序是一种稳定的排序
* @author shuaicenglou
*/
public class MergeSort {
public static void main(String[] args) {
int[] a = {,,,,,,,,,};
sort(a);
for(int i:a) System.out.println(i);
}
/**
* 非递归实现,时间复杂度为O(NlogN),空间复杂度为O(N)
* @param array
*/
public static void sort(int[] array){
/*
* 每次分割的长度都是原来的2倍
*/
for (int gap = ; gap < array.length; gap = * gap) {
mergepass(array, gap, array.length);
}
}
/**
* 归并操作,合并左右数组
* @param array
* @param gap
* @param length
*/
public static void mergepass(int[] array,int gap,int length){
int i=;
// 归并gap长度的两个相邻子表
for (i=;i+*gap-<length;i=i+*gap) {
merge(array,i,i+gap-,i+*gap-);
}
// 余下两个子表,后者长度小于gap
if (i + gap - < length) {
merge(array, i, i + gap - , length - );
}
}
/**
* 合并两个有序数组,R2为临时存储空间
* 如果array[left]>array[right],将array[left]复制到R2,当有一个数组为空时将另一个
* 非空数组剩下的内容复制进临时存储空间R2,将R2替换掉array中的顺序,完成合并
* @param array 待合并的数组
* @param low 左段最低位
* @param mid 左段最高位(右段最低位为mid+1)
* @param high 右端最高位
*/
public static void merge(int[] array,int low,int mid,int high){
int size = high-low+;
int[] R2 = new int[size]; //临时存储空间
int left = low, right = mid+, count = ;
while(left <= mid&&right <= high){
int leftmin = array[left], rightmin = array[right];
if(leftmin <= rightmin){
R2[count++] = leftmin;
left++;
}else{
R2[count++] = rightmin;
right++;
}
}
//将剩下的数字复制进R2
if(left>mid&&right<=high){ //左边数组已空,右边不空
for(int i=right;i<=high;i++){
R2[count++] = array[i];
}
}else{ //包括右边数组已空左边不空等其他情况
for(int i=left;i<=mid;i++){
R2[count++] = array[i];
}
}
for(int i:R2) array[low++] = i;
}
}