|
插入排序（Insertion Sort）的基本思想是每次将一个待排序的记录按其关键字大小插入到前面已经排好序的子文件中的适当位置直到全部记录插入完成为止 直接插入排序 直接插入排序（Straight Insertion Sort）将一个记录插入到排好序的有序表中从而得到一个新的记录数增的有序表 直接插入排序算法 哨兵（监视哨）有两个作用一是作为临变量存放R[i]（当前要进行比较的关键字）的副本二是在查找循环中用来监视下标变量j是否越界 当文件的初始状态不同时直接插入排序所耗费的时间是有很大差异的最好情况是文件初态为正序此时算法的时间复杂度为O(n)最坏情况是文件初态为反序相应的时间复杂度为O(n)算法的平均时间复杂度是O(n)算法的辅助空间复杂度是O()是一个就地排序 直接插入排序是稳定的排序方法 |
