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

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

一.排序方法

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

将待插入元素data[i]从右向左依次与有序区中记录data[j](j=i-1，i-2，…，0)进行比较。若data[j]大于data[i]，则将data[j]后移一个位置。若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;}

?四.时间复杂度和稳定性

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

?

?