java歸并排序算法

/**


歸并排序：里面是一個遞歸程序，深刻理解之。
*/
public class MergeSort {
/**

遞歸劃分數組
*
@param arr
@param from
@param end
@param c
void
*/
public void partition(Integer[] arr, int from, int end) {
// 劃分到數組只有一個元素時才不進行再劃分
if (from < end) {
// 從中間劃分成兩個數組
int mid = (from + end) / 2;
partition(arr, from, mid);
partition(arr, mid + 1, end);
// 合并劃分后的兩個數組
merge(arr, from, end, mid);
}
}
/**

數組合并，合并過程中對兩部分數組進行排序 前后兩部分數組里是有序的
*
@param arr
@param from
@param end
@param mid
@param c
void
*/
public void merge(Integer[] arr, int from, int end, int mid) {
Integer[] tmpArr = new Integer[arr.length];
int tmpArrIndex = 0;// 指向臨時數組
int part1ArrIndex = from;// 指向第一部分數組
int part2ArrIndex = mid + 1;// 指向第二部分數組
// 由于兩部分數組里是有序的，所以每部分可以從第一個元素依次取到最后一個元素，再對兩部分
// 取出的元素進行比較。只要某部分數組元素取完后，退出循環
while ((part1ArrIndex <= mid) && (part2ArrIndex <= end)) {
// 從兩部分數組里各取一個進行比較，取最小一個并放入臨時數組中
if (arr[part1ArrIndex] - arr[part2ArrIndex] < 0) {
// 如果第一部分數組元素小，則將第一部分數組元素放入臨時數組中，并且臨時數組指針
// tmpArrIndex下移一個以做好下次存儲位置準備，前部分數組指針part1ArrIndex
// 也要下移一個以便下次取出下一個元素與后部分數組元素比較
tmpArr[tmpArrIndex++] = arr[part1ArrIndex++];
} else {
// 如果第二部分數組元素小，則將第二部分數組元素放入臨時數組中
tmpArr[tmpArrIndex++] = arr[part2ArrIndex++];
}
}
// 由于退出循環后，兩部分數組中可能有一個數組元素還未處理完，所以需要額外的處理，當然不可
// 能兩部分數組都有未處理完的元素，所以下面兩個循環最多只有一個會執行，并且都是大于已放入
// 臨時數組中的元素
while (part1ArrIndex <= mid) {
tmpArr[tmpArrIndex++] = arr[part1ArrIndex++];
}
while (part2ArrIndex <= end) {
tmpArr[tmpArrIndex++] = arr[part2ArrIndex++];
}
// 最后把臨時數組拷貝到源數組相同的位置
System.arraycopy(tmpArr, 0, arr, from, end - from + 1);
}
/**

測試
*
@param args
*/
public static void main(String[] args) {
 Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7, -1, 0, -5, -2 };
 MergeSort insertSort = new MergeSort();
 insertSort.partition(intgArr, 0, intgArr.length - 1);
 for (Integer a : intgArr) {
 System.out.print(a + " ");

 }
}
}</pre>