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

一.排序方法

     基本思想：被排列的数组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. 直接插入排序是稳定的。