public class MergeSort {
/**
* ans2: 非递归实现
*/
public static void mergeSort2(int[] array) {
if(array == null || array.length < 2) {
return;
}
int step = 1; //初始步长
int len = array.length;
while (step < len) {
int left = 0;
while (left < len) {
int mid = 0;
//左边数组坐标 left...mid
if(len - left > step) { //数组内元素够step个
mid = left + step - 1;
} else {
break; //左边数组都凑不够
}
int right = 0;
//右边数组范围 mid+1 ....right
if(len - mid > step) {
right = mid + step;
} else {
right = len - 1;
}
mergeSortedSubArray(array,left,mid,right); //合并数组
if(right == len - 1) {
break;
} else {
left = right + 1;
}
}
if(step > (len >> 1)) { //为了安全,防止step翻倍之后溢出
break;
} else {
step <<= 1;
}
}
}
/**
* ans1:归并排序递归实现
*/
public static void mergeSort1(int[] array) {
if(array == null || array.length < 2) {
return;
}
process(array,0,array.length-1);
}
//递归调用实现
private static void process(int[] array, int left,int right) {
if(left == right) { //定义递归结束条件
return;
}
//先从中间咔嚓一刀,左右两边分别排序,再合并
int mid = left + ((right - left) >> 1); //防止数组过大时,left+right溢出
process(array,left,mid); //先排左边
process(array,mid+1,right); //再排右边
mergeSortedSubArray(array,left,mid,right);
}
//合并两段排序好的数组
private static void mergeSortedSubArray(int[] array, int left, int mid, int right) {
int[] assist = new int[right-left+1];
int p = left;
int q = mid+1;
int i = 0; //assist的索引
while (p <= mid && q <= right) {
assist[i++] = array[p] < array[q] ? array[p++] : array[q++];
}
//当上边这个循环结束后,说明p和q至少有一个越界了,也就是说至少有一个数组合并完了
//接下来就是合并未处理完的数组中的值,下边两个只会进一个
while (p <= mid) {
assist[i++] = array[p++];
}
while (q <= right) {
assist[i++] = array[q++];
}
//然后把合并后的数组 更新到员数组中
for (int j = 0; j < assist.length; j++) {
array[left+j] = assist[j];
}
}
public static void main(String[] args) {
//测试递归
//ArrayUtil.testArraySorted(100000,50,100,MergeSort.class,"mergeSort1");
int[] ints = ArrayUtil.generateRandomArray(20, 20);
ArrayUtil.printArray(ints);
mergeSort2(ints);
ArrayUtil.printArray(ints);
mergeSort1(ints);
ArrayUtil.printArray(ints);
}
}
标签:归并,right,int,mid,step,array,排序,left
From: https://www.cnblogs.com/xinay/p/16848866.html