1. 递归实现
package pr.cgl.test;
/**
* Created by LL on 2017/5/24.
*/
public class MergeSort {
public static void main(String[] args) {
int[] a = {3, 23, 22, 1, 5, 3, 4, 44, 0};
sort(a, 0, a.length - 1);
}
/**
* 递归调用排序,当切分成只有一个元素时递归结束,即当start=end时
* @param a
* @param start
* @param end
*/
public static void sort(int[] a, int start, int end){
int mid = (start + end) / 2;
if(start < end){
sort(a, start, mid);
sort(a, mid + 1, end);
merge(a, start, mid, end);
}
}
/**
*
* @param a 上次排序完的数组
* @param start
* @param mid
* @param end
*/
public static void merge(int[] a, int start, int mid, int end) {
int[] left = new int[mid - start + 1];
int[] right = new int[end - mid];
int i = 0, j = 0;
for (i = start; i <= mid; i++) {
left[i-start] = a[i];
}
for (j = mid + 1; j <= end; j++) {
right[j - mid - 1] = a[j];
}
int flagL = 0, flagR = 0;
i = start;
while (flagL<left.length && flagR<right.length){
if(left[flagL] < right[flagR]){
a[i] = left[flagL];
flagL ++;
}else{
a[i] = right[flagR];
flagR ++;
}
i++;
}
while(flagL < left.length){
a[i++] = left[flagL++];
}
while(flagR < right.length){
a[i++] = right[flagR++];
}
print(a);
}
public static void print(int[] arr){
System.out.println();
for(int x: arr){
System.out.print(x+" ");
}
}
}
2. 非递归实现
package pr.cgl.test;
/**
* Created by LL on 2017/5/25.
*/
public class MergeSortNoRecursive {
public static void main(String[] args) {
int[] a = {3,23,22,1,5,3,4,44,0};
int len = a.length;
print(a);
execute(a);
int mid = (len-1)/2;
merge(a, 0, mid, len - 1);
print(a);
}
public static void execute(int[] a) {
int len = a.length;
int end = len - 1;
int step = 2;
while(step < len){
int part = 0, s = 0, e = 0;
int parts = len%step==0? len/step: len/step + 1;
while(e <= end && part< parts){
s = step * part;
e = step * (part+1) - 1;
e = e > end? end: e;
int mid = (s + e) / 2;
merge(a, s, mid, e);
part ++;
}
step = step * 2;
}
if(len%2==1){
step = step >> 1;
merge(a, 0, step-1, end);
}
}
public static void merge(int[] data, int start, int mid, int end) {
if(start < end){
int temp[] = new int[data.length];
int i = 0, flagL = start, flagR = mid + 1;
for(i = 0; i <= data.length - 1; i ++){
temp[i] = data[i];
}
i = start;
while(flagL <= mid && flagR <= end){
if(temp[flagL] < temp[flagR]){
data[i] = temp[flagL];
flagL ++;
}else{
data[i] = temp[flagR];
flagR ++;
}
i++;
}
while(flagL <= mid){
data[i++] = temp[flagL++];
}
while (flagR <= end){
data[i++] = temp[flagR++];
}
}
}
public static void print(int[] arr){
System.out.println();
for(int x: arr){
System.out.print(x+" ");
}
}
}