归并排序
1、原理
归并排序是一种概念上最简单的排序算法，与快速排序一样，归并排序也是基于分治法的。归并排序将待排序的元素序列分成两个长度相等的子序列，为每一个子序列排序，然后再将他们合并成一个子序列。合并两个子序列的过程也就是两路归并。
2、复杂度
归并排序是一种稳定的排序算法，归并排序的主要问题在于它需要一个与待排序数组一样大的辅助数组空间。由于归并排序每次划分时两个子序列的长度基本一样，所以归并排序最好、最差和平均时间复杂度都是nlog2n。
public class test1 { public void merge(int []a, int left, int mid, int right) { int []tmp = new int[a.length]; int p1 = left, p2 = mid + 1, k = left; 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 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); } } @Test public void test3() { System.out.println("hello"); int[] a = {49, 38, 65, 97, 76, 13, 27, 50}; mergeSort(a, 0, a.length - 1); System.out.println("ok to sort by time"); for (int e : a) { System.out.print(e + " "); } } }
