算法分析

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．直接插入排序的稳定性
    　直接插入排序是稳定的排序方法。