【手写排序】二路归并排序

/** * <p>@author Jay</p> * <p>@date 2020/9/3 8:43</p> * <p>@Description:</p> * */ public class mergeSort { //两路归并算法，两个排好序的子序列合并为一个子序列 public static void merge(int[] a, int left, int mid, int right) { int[] tmp = new int[a.length];//辅助数组 int p1 = left, p2 = mid + 1, k = left;//p1、p2是检测指针，k是存放指针 while (p1 <= mid && p2 <= right) { if (a[p1] <= a[p2]) tmp[k++] = a[p1++]; else tmp[k++] = a[p2++]; } while (p1 <= mid) tmp[k++] = a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中 while (p2 <= right) tmp[k++] = a[p2++];//同上 //复制回原素组 for (int i = left; i <= right; i++) a[i] = tmp[i]; } public static void mergeSort(int[] a, int start, int end) { if (start < end) {//当子序列中只有一个元素时结束递归 int mid = (start + end) / 2;//划分子序列 mergeSort(a, start, mid);//对左侧子序列进行递归排序 mergeSort(a, mid + 1, end);//对右侧子序列进行递归排序 merge(a, start, mid, end);//合并 } } }

归并排序比较简单，中心思想就是分治，使用递归将模块一直拆分，这里是二路归并排序，所以只需要拆分为两块，递归结束的条件是不可再分，也就是分为一个的时候停止，从第一个开始时将每一个模块当作一个已经排序好的数组，有如双指针，在两个数组头设立指针，进行值的比较，然后插入到新数组中。