11.2 外部排序与选择排序

01外部排序的方法

1、外部排序基本上由两个相对独立的阶段组成。

2、首先，按可用内存大小，将外存上含n个记录的文件分成若干长度为l的子文件或段（segment），依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到到有序子文件重新写入外存，通常称这些有序子文件为归并段或顺串（run）。

3、然后，对这些归并段进行逐趟归并，使归并段（有序的子文件）逐渐由小至大，直至得到整个有序文件为止。

4、一般情况下，外部排序所需总的时间=内部排序（产生初始归并段）所需的时间+外存信息读写的时间+内部归并所需的时间。

01置换-选择排序

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

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

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

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

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

C语言 | 函数实现比较大小

更多案例可以go公众号：C语言入门到精通