分配排序

题目描述

分配排序，也称多路快速排序，核心思想和快排一样。快排的思想是找一个分点把数据分成两半，把比分点小的放在前面，比分点大的放在后面，然后对这两个部分分别进行快排递归。与归并排序类似，对于外排序方法，数组不是划分成两半，而是根据外存算法的特点划分成多个部分。其思想是对未排序的列表可以使用小于M/B个分割元素，通过扫描一次I/O实现划分,然后对划分的每一块再进行递归划分，直到最后的划分能存进内存为止。设计一个程序体现外存分配排序的基本算法思想并量化验证算法复杂度。