 多路树查找－外部查找(B树)【源代码】多路树查找－外部查找(B树)【下载及演示说明】双向链表演示程序【下载及演示说明】循环链表演示程序【下载及演示说明】链表【讲解】动态存储分配之边界标识法演示程序【下载及演示说明】动态存储分配之边界标识法【讲解】首次适应算法和最佳适应算法【讲解】动态存储分配之边界标识法【源代码】振荡排序算法【讲解】振荡排序演示程序【下载及演示说明】树和二叉树相互转化【讲解】深度优先搜索【下载及演示说明】深度优先搜索【源代码】朴素字符串匹配演示程序【下载及演示说明】当前1/4页 首页 上一页 下一页 尾页 | |
算法讲堂 |
|
本栏目所有文章由本站组织业内技术专家原创而成，用汇编语言向学习者讲解经典问题的编程思想和编程方法。 本栏目所有文章的版权归本站所有，转载请注明出处为汇编网<www.asmedu.net> 。 现本栏目的内容处于不断添加中，请随时关注。 |
|
| 算法讲堂－》振荡排序算法【讲解】 |
|
算法介绍：
振荡排序是外部排序的一种。外部排序与内部排序十分不同，对于外部排序来说，必须把数据的结构合理安排，使得相当慢的外部存储（磁带、磁盘等）能快速地满足排序算法的要求。 首先，我们先要明确一下在外部排序中的一个名词--路段。路段是指通过初始的内部排序阶段产生的记录的递增序列。也就是说，路段是一个经内部排序调整后的记录，这个记录是递增顺序的。比如说，“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.模拟利用四条或五条磁带进行震荡排序。 [07/10/16] |