数据结构-插入排序

插入排序

思路：

插入排序的工作方式类似于扑克牌游戏的摸牌阶段，每次从桌子上摸一张牌，同时按扑克牌的大小顺序，找到合适的位置，插入达到从小到大的排列顺序。

如何借助上述思想实现排序呢？我们将数组中的数据分为两个区间----①已经排序的区间②未排序的区间。
初始已排序的区间只有第一个元素值，即数组中的第一个元素，然后在未排序区间中依次取出元素并插入到已排序数组中的合适位置，保证已排序区间始终有序，重复以上操作直到未排序区间元素为空，就可以实现啦！

代码实现：

	private static void insertSort(int[] array)// 快速排序
	{
		// a[i]为原数组，a[j]为排序好的新数组
		int len = array.length;
		for (int i = 1; i < len; i++) {
			int key = array[i];
			int j = i - 1;

			while (j >= 0 && array[j] > key) {
				array[j + 1] = array[j];
				j--;
			}
			array[j + 1] = key;
		}
	}

性能分析：
最坏时间复杂度–O(n2)
如果数组为倒序排列，每次插入相当于在数组头部插入新的元素值，这样每插入一个新的元素值key，相当于key要和所有的已排序的数组元素进行比较。所以时间复杂度为O(n2)
最好时间复杂度–O(n)
如果数组为正序排列，每次插入key值，相当于key值只需要和已排序数组中最大的元素比较一次即可。所以时间复杂度为O(n)