11.4 置换-选择排序

01

置换-选择排序

1、归并的趟数不仅和k成反比，也和m成正比，因此，减少m是减少s的另一种途径。

2、内排方法是在内排过程中移动记录和对关键字进行比较都是在内存中进行的。

3、置换-选择排序（Replacement-Selection Sorting）是在树形选择排序的基础上得来的，它的特点是：在整个排序（得到所有初始归并段）的过程中，选择最小（或最大）关键字和输入、输出交叉或平行进行。

4、置换-选择排序所得初始归并段的长度不等。且当输入文件中记录的关键字为随机数时，所得初始归并段的平均长度为内存工作区大小的两倍。

5、若不计输入、输出的时间，则对n个记录的文件而言，生成所有初始归并段所需时间为O（nlogw）。