严蔚敏数据结构排序.ppt

算法描述 算法评价 时间复杂度最坏情况下T(n)=O(nlogn) 空间复杂度S(n)=O(1) 9.4 归并排序 归并将两个或两个以上的有序表组合成一个新的有序表叫~ 2-路归并排序 排序过程 设初始序列含有n个记录则可看成n个有序的子序列每个子序列长度为1 两两合并得到?n/2?个长度为2或1的有序子序列 再两两合并如此重复直至得到一个长度为n的有序序列为止 将下属两个已排序的顺序表合并成一个