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

TTdreamloong 2012-11-06

一.排序方法

     基本思想:被排列的数组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. Cmin=n-1=0(n)
    3. Mmin=0
    4. 直接插入排序最好的时间复杂度为O(n)
  2. 最坏时间复杂度
    1. 若初始文件是反序的,所需的关键字比较次数C和记录移动次数M。
    2. Cmax=(n+2)(n-1)/2=O(n2)
    3. Mmax=(n-1)(n+4)/2=O(n2)
    4. 直接插入排序的最坏时间复杂度为O(n2)
  3. 平均时间复杂度
    1. O(n2)
  4. 算法的空间复杂度:算法所需的辅助空间是一个监视哨,辅助空间复杂度S(n)=O(1)。是一个就地排序。
  5. 直接插入排序是稳定的。

相关推荐