public class MergeSort {
static int number=0;
public static void main(String[] args) {
int[] a = {26, 5, 98, 108, 28, 99, 100, 56, 34, 1 };
printArray("排序前：",a);
MergeSort(a);
printArray("排序后：",a);
}
private static void printArray(String pre,int[] a) {
System.out.print(pre+"\n");
for(int i=0;i
System.out.print(a[i]+"\t");
System.out.println();
}
private static void MergeSort(int[] a) {
// TODO Auto-generated method stub
System.out.println("開始排序");
Sort(a, 0, a.length - 1);
}
private static void Sort(int[] a, int left, int right) {
if(left>=right)
return;
int mid = (left + right) / 2;
//二路歸并排序里面有兩個Sort，多路歸并排序里面寫多個Sort就可以了
Sort(a, left, mid);
Sort(a, mid + 1, right);
merge(a, left, mid, right);
}
private static void merge(int[] a, int left, int mid, int right) {
int[] tmp = new int[a.length];
int r1 = mid + 1;
int tIndex = left;
int cIndex=left;
// 逐個歸并
while(left <=mid && r1 <= right) {
if (a[left] <= a[r1])
tmp[tIndex++] = a[left++];
else
tmp[tIndex++] = a[r1++];
}
// 將左邊剩余的歸并
while (left <=mid) {
tmp[tIndex++] = a[left++];
}
// 將右邊剩余的歸并
while ( r1 <= right ) {
tmp[tIndex++] = a[r1++];
}
System.out.println("第"+(++number)+"趟排序:\t");
// TODO Auto-generated method stub
//從臨時數組拷貝到原數組
while(cIndex<=right){
a[cIndex]=tmp[cIndex];
//輸出中間歸并排序結果
System.out.print(a[cIndex]+"\t");
cIndex++;
}
System.out.println();
}
}
)
