数据结构考研纲要

85.排序总结(1)快排最优，需要递归栈；归并需要使用较多空间用于元素复制(2)直插、冒泡有序时O(n)；平均和最坏O()(3)简单选择最差：O()；有序情况比较次数不变；但是不移动；最坏3(n-1)次移动(4)堆排序O(n)；无论时间、空间；数据各方面最好；平均性能不如快排(5)稳定：直插、冒泡、归并、基数(6)若n较小；采用直插和简单选择；直插需要移动位置，所以数据信息量大时不好(7)若基本有序；采用直插、冒泡；完全有序时只需比较n-1次；不需要交换(8)中等规模：希尔排序很好的选择；但是不稳定(9)n较大：快排；归并；堆排序；要求稳定选归并，然后先直插结合，然后再归并86.外部排序(1)文件较大，内存一次放不下(2)两个阶段：