插入&希尔&归并排序算法

通常我们从下面几个方面来分析一个排序算法：

1. 时间复杂度 ：时间效率决定了算法运行多久，O（1）
2. 空间复杂度：
3. 比较次数&交换次数：排序肯定会牵涉到两个操作，比较和交换。
4. 稳定性：相同的两个数排完序后，相对位置不变。

插入排序，希尔排序，归并排序这三种排序方式其实是依次优化的，希尔排序是插入排序的一种升级，归并排序是插入算法的升级，效率比希尔排序还好。

一、插入排序 1、算法描述

插入排序也是一种常见的排序算法。

插入排序的思想：

将初始数据分为有序部分和无序部分，每一步将一个无序部分的数据插入到前面已经排好序的有序部分中，直到插完所有元素为止。

插入排序的步骤如下：

1. 将将数组分为两段，数组分成有序数组段和无序数组段。初始化时有序数组段只有一个元素。
2. 每次从无序数组中取出一个元素，与有序数组中的元素从后向前依次进行比较，直到找到合适的位置，然后该元素插到有序数组中，即保证插入后有序数组段仍然有序。
3. 重复执行上述操作，直到无序数组段全部插入完成。

时间复杂度: O(n^2)

稳定性 ：稳定

2、示例

生活中有很多类似于插入排序的行为，例如打扑克。 比如我们对 7, 8, 6, 9, 0, 4, 3进行插入排序

• step1：7为有序数组段，8 9 0 4 3为无序数组段。
• step2：取出 8 和 7比较，发现 8>7，所以不用交换，即： 7 8 6 9 0 4 3
• step2：取出 6，依次与前面的7和8比较 ，则6放在 7的前面，即： 6 7 8 9 0 4 3
• step3：取出 9，依次与前面的比较，因为9大，所以不用交换，即：6 7 8 9 0 4 3
• …
• 最终得到：0 3 4 6 7 8 9

从以上操作中我们看到插入排序会经历一个元素的比较以及元素的移动。

当我们每次从无序数组中取出一个元素，与有序数组中的元素从后向前依次进行比较，直到找到合适的位置，然后该元素插到有序数组中，并将有序数组段中插入点之后的元素进行往后移动。

代码如下：

	public static void main(String[] args) {
		int[] array = {7, 8, 6, 9, 0, 4, 3};
		insertionSort(array);
		System.out.println("最终排序结果为：" + Arrays.toString(array));
	}

	private static void insertionSort(int[] array) {
		if (array == null || array.length