直接插入排序

源文章URL:http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.2.1.1.htm

做过部分修改。

 

1、基本思想
    　假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。

 

2．具体做法

    　将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j](j=i-1，i-2，…，1)的关键字进行比较：
    　① 若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置；
       ②若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。
    　关键字比R[i]的关键字大的记录均已后移，所以j+1的位置已经腾空，只要将R[i]直接插入此位置即可完成一趟直接插入排序。

 

 

void sort(int R[],int n)//直接插入排序（从小到大） { for(int i = 1; i < n; i++) { int sentinel = R[i]; int j = i - 1; while(j >= 0 && R[j] > sentinel) { R[j+1] = R[j--]; } R[j+1] = sentinel; } } 

 

算法分析

1．算法的时间性能分析 
    　对于具有n个记录的文件，要进行n-1趟排序。
    各种状态下的时间复杂度：
┌─────────┬─────┬──────┬──────┐
│ 初始文件状态     │   正序   │     反序   │无序(平均)  │
├─────────┼─────┼──────┼──────┤
│ 第i趟的关键      │   1      │     i+1    │ （i-2）/2  │
│ 字比较次数       │          │            │            │
├─────────┼─────┼──────┼──────┤
│总关键字比较次数  │   n-1    │(n+2)(n-1)/2│ ≈n²/4     │
├─────────┼─────┼──────┼──────┤
│第i趟记录移动次数 │   0      │ i+2        │ （i-2）/2  │
├─────────┼─────┼──────┼──────┤
│总的记录移动次数  │   0      │(n-1)(n+4)/2│ ≈n²/4     │
├─────────┼─────┼──────┼──────┤
│时间复杂度        │  0（n）  │ O（n²）    │ O（n²）    │
└─────────┴─────┴──────┴──────┘
注意：
    　初始文件按关键字递增有序，简称"正序"。
　    初始文件按关键字递减有序，简称"反序"。 

2．算法的空间复杂度分析
    　算法所需的辅助空间是一个监视哨，辅助空间复杂度S(n)=O(1)。是一个就地排序。

3．直接插入排序的稳定性
    　直接插入排序是稳定的排序方法。