合併排序法 (Java)

說明：

• 1. 將陣列等分成 2 群，【 左群 】 及 【 右群 】 。

  2. 分別排序【 左群 】 及 【 右群 】 。

  3. 合併排序後【 左群 】 及 【 右群 】 。

  4. 遞迴呼叫分群 (1) 直至群個數剩下 1 或 2 個元素為止開始排序 。

原始碼：

package com.Emprogria; import java.util.ArrayList; /** * * @author Rich Lee */ public class MergeSort { private ArrayList<Integer> numList = null; private int seqNum = 0; public MergeSort() { this.numList = new ArrayList<Integer>(); } public void initiateMergeSort(int numList[]) { this.numList.clear(); for (int i = 0; i < numList.length; i++) { this.numList.add(numList[i]); } this.seqNum = 0; } private int getMidPos(int start, int end) { int mid = (end - start + 1) / 2; return start + mid; } public void doMerge(int start, int end) { ArrayList<Integer> tempNumList = new ArrayList<Integer>(); int mid = this.getMidPos(start, end); for (int i = 0, j = 0, k = 0; (i <= end - start); i++) { if (mid + k + 1 > end) { tempNumList.add(this.numList.get(start + j++)); continue; } if (j > mid) { tempNumList.add(this.numList.get(mid + 1 + k++)); continue; } if (this.numList.get(start + j) > this.numList.get(mid + k + 1)) { tempNumList.add(this.numList.get(mid + 1 + k++)); } else { tempNumList.add(this.numList.get(start + j++)); } } for (int i = start; i <= end; i++) { this.numList.set(i, tempNumList.get(i - start)); } } private void swapValues(int start, int end) { int tempValue = this.numList.get(start); this.numList.set(start, this.numList.get(end)); this.numList.set(end, tempValue); } public void doSoft(int start, int end) { int mid = this.getMidPos(start, end); if (end == start) { return; } if (end - start == 1) { if (this.numList.get(start) > this.numList.get(end)) { this.swapValues(start, end); } return; } System.out.printf("\t(%d) %d~%d, %d~%d\n", ++this.seqNum, start, mid, mid + 1, end); this.doSoft(start, mid); this.doSoft(mid + 1, end); this.doMerge(start, end); } public void showList() { for (int i = 0; i < this.numList.size(); i++) { System.out.printf("%d ", this.numList.get(i)); } System.out.println(); } /** * @param args the command line arguments */ public static void main(String[] args) { int numList[] = {20, 2, 18, 3, 5, 17, 6, 17, 11, 4, 9}; MergeSort myMergeSort = new MergeSort(); myMergeSort.initiateMergeSort(numList); myMergeSort.showList(); myMergeSort.doSoft(0, numList.length - 1); myMergeSort.showList(); } }