置换-选择排序

如下图，内存工作区 WA 是一个自动维护的小根堆结构。我们每次都可以很快的找到 WA 中的最小的元素。

再维护一个变量为 minMAX 表示 FO 的最大值。

如果 WA 的最小元素大于 minMAX，那么就直接加到初始归并段的后面。反之，就标记停留在 WA 中。如果 WA 空间已满，且不能弹出元素，就关闭当前的初始段。新开一个初始段。

![[8.7.4置换-选择排序.mp4]]