数据结构与算法学习三：直接插入排序

一.排序方法

     基本思想：被排列的数组data[0...n]。初始时，data[0]自成1个有序区，无序区为data[1..n]；从i=1起直至i=n为止，依次将data[i]插入当前的有序区data[0..i-1]中，生成含n个记录的有序区。

1. 将待插入元素data[i]从右向左依次与有序区中记录data[j](j=i-1，i-2，…，0)进行比较。
2. 若data[j]大于data[i]，则将data[j]后移一个位置。
3. 若data[j]小于或等于data[i]，则查找过程结束，j+1即为data[i]的插入位置。

二.动画演示

     http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/insertsort.htm

三.Java代码

public static int[] insertSort(int[] data) {
		int temp = 0;
		for (int i = 1; i < data.length; i++) {
			if (data[i - 1] > data[i]) {
				temp = data[i];
				int j = i - 1;
				for (; j >= 0 && data[j] > temp; j--) {
					data[j + 1] = data[j]; // 后移
				}
				data[j + 1] = temp;
			}
		}
		return data;
	}

 四.时间复杂度和稳定性

1. 最好时间复杂度
   1. 若文件的初始状态是正序的，所需的关键字比较次数C和记录移动次数M。
   2. C_min=n-1=0(n)
   3. M_min=0
   4. 直接插入排序最好的时间复杂度为O(n)
2. 最坏时间复杂度
   1. 若初始文件是反序的，所需的关键字比较次数C和记录移动次数M。
   2. C_max=(n+2)(n-1)/2=O(n²)
   3. M_max=(n-1)(n+4)/2=O(n²)
   4. 直接插入排序的最坏时间复杂度为O(n²)
3. 平均时间复杂度
   1. O(n²)
4. 算法的空间复杂度：算法所需的辅助空间是一个监视哨，辅助空间复杂度S(n)=O(1)。是一个就地排序。
5. 直接插入排序是稳定的。