package com.edu.hpu.sort.merge;
import com.edu.hpu.sort.Sort;
public class MergeSort extends Sort {
@Override
public int[] doSort(int[] arr) {
return mergeSort2(arr, 0, arr.length - 1);
}
@SuppressWarnings("unused")
private int [] mergeSort(int [] arr, int p, int r){
if(p < r){
int q = (p + r) / 2;
mergeSort(arr, p, q);
mergeSort(arr, q + 1, r);
merge(arr, p, q, r);
}
return arr;
}
// 归并排序非递归
private int [] mergeSort2(int [] arr, int p, int r){
int [] res = new int[arr.length];
int index = 0;
// 表示每次归并完后有多少个元素无法进行归并
int last = 0;
int w = 0;
// 每次归并的个数
for(int j = 2; j <= arr.length; j *= 2){
// 每次将多余的元素,不能进行但不归并的放入另外的辅助数组中去,原数组的长度将去放入的长度。
for(int i = 0; i < arr.length - last && w < arr.length; i += j){
if(arr.length - i >= j) {
int q = (i + i + j -1) / 2;
// 归并
merge(arr, i, q, i + j - 1);
}else{
// 对辅助数组的元素进行归并处理
index = w;
for(int v = i; v < arr.length - index; v++){
res[w] = arr[v];
//arr[v] = 0;
w++;
last = w;
}
// 对辅助数组进行归并
res = merge(res, 0, index - 1, w - 1);
}
}
}
for(int i = 0; i < arr.length - last; i++){
res[last + i] = arr[i];
}
//两个数组归并
arr = merge(res, 0, last - 1, res.length - 1);
return arr;
}
private int [] merge(int [] arr, int p, int q, int r){
// 多加一个位置是为了安放一个哨兵
int [] letf = new int[q - p + 1 + 1];
int [] right = new int[r - q + 1];
// 放入哨兵
letf[letf.length - 1] = Integer.MAX_VALUE;
right[right.length - 1] = Integer.MAX_VALUE;
int i = 0, j = 0;
// 初始化数组
for( ; i < letf.length - 1; i++){
letf[i] = arr[p + i];
}
for( ; j < right.length - 1; j++){
right[j] = arr[q + j + 1];
}
// 对两个数组进行归并
i = 0; j = 0;
for(int k = p; k <= r; k++){
if(letf[i] < right[j]){
arr[k] = letf[i];
i++;
}else{
arr[k] = right[j];
j++;
}
}
return arr;
}
public static void main(String[] args) {
MergeSort mergeSort = new MergeSort();
mergeSort.printOrder(new int []{90, 4342,89, 0, 8,90,45,8,23,1,0,43242,43,432,54,543,45431,321,8,8,9,1,7,8,777,5});
}
}