振荡排序算法

xingke

振荡排序是外部排序的一种。外部排序与内部排序十分不同，对于外部排序来说，必须把数据的结构合理安排，使得相当慢的外部存储（磁带、磁盘等）能快速地满足排序算法的要求。
首先，我们先要明确一下在外部排序中的一个名词--路段。路段是指通过初始的内部排序阶段产生的记录的递增序列。也就是说，路段是一个经内部排序调整后的记录，这个记录是递增顺序的。比如说，“abc”可以是一个路段，但“acb”则不是一个路段。
其次，我们要理解一个多路合并的概念。多路合并是外部排序经常要用到的一个方法。它解决了在内存储设备的空间不足的情况下，将大的记录进行排序形成新的有序记录的问题，下面举例说明。
假设，通过容量为100的一个内部存储对数据量为500的一个记录排序。
根据上述可以分析到，该记录可以平均分成5个路段（路段形成的排序过程属内部排序过程），我们假设有四条磁带（外存储介质）进行合并，合并的过程如下：
（1）向磁带1和磁带2上交替分布5个路段，该过程称作分布，如下
磁带1：R1-100 ， R201-300 ，R401-500
磁带2：R101-200 ， R301-400
磁带3：（空）
磁带4：（空）
（2）合并操作，将磁带1和磁带2相应位置上的路段进行合并，形成新的路段，写到磁带3和磁带4上，如下：
磁带3：R1-200 ，R401-500
磁带4：R201-400
（3）利用上面两步的原理，将磁带3和磁带4上的路段合并到磁带1和磁带2，如下
磁带1：R1-400  
磁带2：R401-500  
（4）最后在磁带3上产生最终合并的结果，如下
磁带3：R1-500
   至此，该合并的过程完成，最后的合并结果是一个递增顺序的记录。
    到此，振荡排序的预备知识差不多了。接着就来介绍一下振荡排序。与其说振荡排序是一种排序算法，不如说是一个处理排序问题的思想更贴切。和把所有初始路段分散到磁带的一个分布之后开始合并操作相比较，振荡排序是在分布与合并之间前后振荡。比如我们现在有4个初始路段（A1，A2，A3，A4），利用3条磁带（T1，T2，T3）进行振荡排序，排序过程如下：
         操作     T1         T2            T3
阶段1：  分布     A1         A2            —
阶段2：  合并     —          —              A1-2
阶段3：  分布     A4         —            A1-2A3
阶段4：  合并     —         A3-4           A1-2
阶段5：  合并     A1-4        —            —

    以上只是对振荡排序进行应用的一个简单的例子，但是很客观的体现出了振荡排序的算法设计原理。这种振荡的过程使得在对输入进行完备地考察之前，许多排序都可以进行。
学习建议及任务：
振荡排序的算法中，实现的是三条磁带的简单振荡排序过程。建议学习者在理解算法的基础上，完成一个振荡排序算法，基本要求如下：
1.排序的记录为不少于100个字符的串。
2.排序中，假设内部存储设备最大容量为10个字符。
3.模拟利用四条或五条磁带进行震荡排序。

vecri

外部排序没怎么学, 当初主要学的是内部排序。.
不过PYG研究算法的好少啊..很少见到关于算法的东西。.~