数据结构-排序-归并排序

归并实现原理：

尽可能的将一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每一个子组的元素个数是1为止。将相邻的两个子组进行合并成一个有序的大组。不断重复步骤 2 和 步骤 3， 直到最终只有一个组为止。

归并排序算法实现：（稳定排序）

public static void main(String[] args) { // 测试 int[] arr = {8, 4, 5, 7, 1, 3, 6, 2}; sort(arr); for (int i : arr) { System.out.print(i+"\t"); } } /* * 归并排序 */ // 辅助数组 private static int[] assist; // 找出两个位置的最小值 private static boolean less(int v, int w) { return v < w; } // 交换数组中两个位置的值 private static void exch(int[] a, int i, int j) { int temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } public static void sort(int[] a) { // 1. 初始化辅助数组 assist = new int[a.length]; // 2. 定义lo和hi变量，分别记录数组中最小值和最大值元素的索引 int lo = 0; int hi = a.length - 1; // 3. 调用sort重载方法完成数组a中，从索引lo到索引hi元素的排序 sort(a, lo, hi); } private static void sort(int[] a, int low, int height) { // 1. 做安全性校验 if (height <= low) { return; } // 2. 对low到height之间的数据进行分为两个组 int mid = low + (height - low) / 2; // 3. 分别对每一组数据进行排序 sort(a, low, mid); sort(a, mid + 1, height); // 4. 再把两个组中的数据进行归并 merge(a, low, mid, height); } private static void merge(int[] a, int low, int mid, int height) { // 定义三个指针 int i = low; int p1 = low; int p2 = mid + 1; // 移动指针p1和p2，比较对应索引处的值，找出小的那个放到辅助数组的对应索引出 while (p1 <= mid && p2 <= height) { // 比较对应索引处的值 if (less(a[p1], a[p2])) { assist[i++] = a[p1++]; } else { assist[i++] = a[p2++]; } } // 遍历，如果p1指针没有走完，那么顺序移动p1指针，把对应元素放到辅助数组的对应索引处 while (p1 <= mid) { assist[i++] = a[p1++]; } // 遍历，如果p2指针没有走完，那么顺序移动p1指针，把对应元素放到辅助数组的对应索引处 while (p2 <= height) { assist[i++] = a[p2++]; } // 把辅助数组中的元组复制到原数组中 for (int index = low; index <= height; index++) { a[index] = assist[index]; } }