插入排序

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的位置

 

包括：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。

 

基本思想：

 

将n个元素的数列分为已有序和无序两个部分，如

 下所示：

　　{，{a2，a3，a4，…,an}}

　　{{a1(1)，a2(1)}，{a3(1)，a4(1) …,an(1)}}

　　…

　　{{a1(n-1)，a2(n-1) ，…}, {an(n-1)}}

　　每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。

 

算法的复杂度：

      如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。

 

java实现：

 

 

/**
	 * 插入排序，适用于少量数据的排序，时间复杂度O(n2)，是稳定的排序算法，原地排序
	 * 
	 * @param a
	 */
	public static void insertSort(int[] a) {
		int length = a.length;

		for (int i = 1; i < length; i++) {
			int temp = a[i];
			int j = i;
			for (; j > 0 && a[j - 1] > temp; j--) {
				a[j] = a[j - 1];
			}
			a[j] = temp;
		}
	}