1、排序算法概述

常用的内部排序方法有：交换排序（冒泡排序、快速排序）、选择排序（简单选择排序、堆排序）、插入排序（直接插入排序、希尔排序）、归并排序、基数排序（一关键字、多关键字）。

• 所需辅助空间最多：归并排序
• 所需辅助空间最少：堆排序
• 平均速度最快：快速排序
• 不稳定：快速排序，希尔排序，堆排序。

选择排序算法的依据：任何排序算法在数据量小的时候基本体现不出来差距。选择依据有：

• 1.数据的规模 ：当数据规模较小时，选择直接插入排序或冒泡排序。
• 2.数据的类型 ：如全部是正整数，那么考虑使用桶排序为最优。
• 3.数据已有的顺序 ：快排是一种不稳定的排序（当然可以改进），对于大部分排好的数据，快排会浪费大量不必要的步骤。

数据量极小，而且已经基本排好序，冒泡是最佳选择。我们说快排好，是指大量随机数据下，快排效果最理想。而不是所有情况。

2、归并排序时空复杂度

最好最差时间复杂度均为O(nlogn)，平均时间复杂度O(nlogn)，空间复杂度O(n)，是一种稳定的排序算法。

• 时间复杂度：对长度为n的文件，需进行趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlogn)。

• 空间复杂度：需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。

3、归并排序原理

归并排序 (merge sort) 是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。

• 归并排序是一种概念上最简单的排序算法，与快速排序一样，归并排序也是基于分治法的。归并排序将待排序的元素序列分成两个长度相等的子序列，为每一个子序列排序，然后再将他们合并成一个子序列。合并两个子序列的过程也就是两路归并。

4、归并排序思路

分而治之(divide - conquer);每个递归过程涉及三个步骤：

• 第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素。
• 第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作。
• 第三, 合并: 合并两个排好序的子序列,生成排序结果。

动图展示：

5、归并排序举例说明

1.归并排序的流程：

2.合并两个有序数组的流程

6、归并排序代码

public class MergeSort {
	
	// 两路归并算法，两个排好序的子序列合并为一个子序列
	public static void merge(int[] a, int low, int mid, int high) {
		int[] tmp = new int[a.length];// 辅助数组
//		int[] tmp = new int[high-low+1];
		int p1 = low, p2 = mid + 1, k = low;// p1、p2是检测指针，k是存放指针
		// 把较小的数先移到新数组中
		while (p1 <= mid && p2 <= high) {
			tmp[k++] = a[p1] <= a[p2] ? a[p1++] : a[p2++];
		}
		// 上面的循环退出后，把剩余的元素依次填入到temp中
	    // 以下两个while只有一个会执行
		// 把左边剩余的数移入数组
		while (p1 <= mid) {
			tmp[k++] = a[p1++];// 如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
		}
		// 把右边边剩余的数移入数组
		while (p2 <= high) {
			tmp[k++] = a[p2++];// 同上
		}
		// 复制回原数组  // 把新数组中的数覆盖nums数组
		for (int i = low; i <= high; i++) {
			a[i] = tmp[i];
		}
	}

	public static void mergeSort(int[] a, int start, int end) {
		if (start < end) {// 当子序列中只有一个元素时结束递归
//			int mid = (start + end) / 2;// 划分子序列
			int mid = start + ((end - start) >> 1);
//			System.out.println(start+"-"+mid+"-"+end);
			mergeSort(a, start, mid);// 对左侧子序列进行递归排序
			mergeSort(a, mid + 1, end);// 对右侧子序列进行递归排序
			merge(a, start, mid, end);// 左右归并
		}
	}
	
	public static void main(String[] args) {
		int[] arr = { 6, 3, 8, 2, 9, 1,7,4 };
		System.out.print("排序前的数组为：");
		for (int num : arr) {
			System.out.print(num + " ");
		}
		mergeSort(arr, 0, arr.length-1);
		System.out.println();
		System.out.print("排序后的数组为：");
		for (int num : arr) {
			System.out.print(num + " ");
		}
	}
}

// 排序前的数组为：6 3 8 2 9 1 7 4 
// 排序后的数组为：1 2 3 4 6 7 8 9