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

归并排序

·先两个一组排序形成(n+)/组再将两组并一组直到剩下一组为止

·归并排序是非就地稳定排序时间复杂度是O(nlogn)

分配排序

箱排序

·按关键字的取值范围确定箱子数按关键字投入箱子链接所有非空箱

·箱排序的平均时间复杂度是线性的O(n)

基数排序

·从低位到高位依次对关键字进行箱排序

·基数排序是非就稳定的排序时间复杂度是O(d*n+d*rd)

各种排序方法的比较和选择

·待排序的记录数目nn较大的要用时间复杂度为O(nlogn)的排序方法

·记录的大小(规模)记录大最好用链表作为存储结构而快速排序和堆排序在链表上难于实现

·关键字的结构及其初始状态

·对稳定性的要求

·语言工具的条件

·存储结构

·时间和辅助空间复杂度

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