常用数据结构有哪些 09年自考《数据结构》各章要点二[6]

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

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

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

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

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

　　插入排序

　　·直接插入排序

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

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

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

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

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

　　希尔排序

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

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

　　交换排序