09年自考《数据结构》各章要点二[6]

经过排序后这些具有相同关键字的记录之间的相对次序保持不变则称这种排序方法是稳定的否则排序算法是不稳定的

排序过程中不涉及数据的内外存交换则称之为内部排序(内排序)反之若存在数据的内外存交换则称之为外排序

内部排序方法可分五类插入排序选择排序交换排序归并排序和分配排序

评价排序算法好坏的标准主要有两条执行时间和所需的辅助空间另外算法的复杂程序也是要考虑的一个因素

插入排序

·直接插入排序

·逐个向前插入到合适位置

·哨兵(监视哨)有两个作用

·作为临变量存放R[i]

·是在查找循环中用来监视下标变量j是否越界

·直接插入排序是就地的稳定排序时间复杂度为O(n^)比较次数为(n+)(n)/;移动次数为(n+)(n)/

希尔排序

·等间隔的数据比较并按要求顺序排列最后间隔为

·希尔排序是就地的不稳定排序时间复杂度为O(n^)比较次数为(n^)移动次数为(n^)

交换排序

[] [] [] [] [] [] [] [] [] [] [] []