在诸多排序算法中，归并排序号称是仅次于快速排序的一种算法。
其算法原理是，不断地将待排序数组划分为两部分，直到子数组不能再分时，再对子数组两两之间进行有序合并Merge（实现一步小范围排序），合并后的多个数组继续进行两两的有序合并Merge。不断将子数组合并为原始长度的大数组，此时的大数组即是归并排序得到的数组。
归并排序的过程就是一个通过递归来求解的过程，先不断进行问题分解（stage1 递推），即两个子数组的排序（及子数组的子数组的排序），最后再将排序的子数组合并为原数组的排序数组（stage2 回归）。
但递归往往效率较低，那么怎么用非递归来实现归并排序呢？
这里的归并排序的子问题分解，其实是一个广度搜索的问题，我们可以借助两个队列Queue的数据结构来实现。
以下是Java编写的递归版归并排序和非递归版归并排序。
import java.util.*; public class Sort { public static void main(String[] args) { Sort main = new Sort(); //测试 int[] array = {12, 1, 5, 9, 8, 6, 2, 5, 5, 6, 9, 10, 3}; System.out.println("Before Sort: " + Arrays.toString(array)); main.mergeSort(array); System.out.println("After Sort: " + Arrays.toString(array)); } private void mergeSort(int[] arr) { mergeSortLoop(arr, 0, arr.length - 1); } /* 递归版本 */ private void mergeSortRecur(int[] arr, int left, int right) { if (left >= right) return; int mid = (left + right) >> 1;//中点 mergeSortRecur(arr, left, mid); mergeSortRecur(arr, mid + 1, right); merge(arr, left, mid, right); } /* 非递归版本 */ private void mergeSortLoop(int[] arr, int left, int right) { if (left >= right) return; LinkedList<int[]> queue4M = new LinkedList<>();//用于记录数组合并的节点位置 Queue<int[]> queue = new LinkedList<>();//用于子问题分解 queue.offer(new int[]{left, right}); while (!queue.isEmpty()) { int[] pair = queue.poll(); left = pair[0]; right = pair[1]; int mid = (left + right) >> 1; if (left < right) {//继续入栈 [1 2]分割 [1]不分割 queue.offer(new int[]{left, mid}); queue.offer(new int[]{mid + 1, right}); queue4M.add(new int[]{left, mid, right});// } } while (!queue4M.isEmpty()) { int[] pair = queue4M.removeLast();//重要，必须从队列尾部开始归并 merge(arr, pair[0], pair[1], pair[2]); } } /*通用有序数组合并, 递归、非递归都要用到*/ private void merge(int[] arr, int left, int mid, int right) { //(left, mid) (mid+1, right) if (right == left) return;//一个数 int n = right - left + 1;//合并段的段程 int[] temp = new int[n]; int idl = left, idr = mid + 1, idt = 0; while (idl <= mid && idr <= right) { if (arr[idl] <= arr[idr]) { temp[idt++] = arr[idl++]; } else { temp[idt++] = arr[idr++]; } } while (idl <= mid) { temp[idt++] = arr[idl++]; } while (idr <= right) { temp[idt++] = arr[idr++]; } for (int i = 0; i < n; i++) { arr[left + i] = temp[i]; } System.out.println(Arrays.toString(temp));//排序和归并过程! } }END 2020-9-4
