归并方式的多线程快速排序算法.pdfVIP

第 8 期 计 算 机 教 育 2010 年 4 月 25 日 Computer Education No.8 Apr.25,2010 149 文章编号：1672-5913(2010)08-0149-04 中图分类号：G642 文献标识码：A 归并方式的多线程快速排序算法 宋鸿陟，傅 熠，肖 磊，张丽霞，邓展鸿 (华南农业大学 信息学院 人机交互研究中心，广东 广州 510642) 摘 要：本文基于 Java 平台针对经典快速排序提出改进方案，使用归并的思想对快速排序作了多线程优化， 并对单、多线程下的快速排序进行了对比测试和分析。结果表明，通过多线程优化，快速排序在双核主机上 对 5 千万个随机整型数据进行排序的速度是单线程的 1.6 倍，说明了该优化方法的有效性。该方法思路直观、 容易理解，宜作为多核技术教学案例。 关键词：快速排序；归并；多线程 1 快速排序 枢轴，另一个子序列里的关键字全部不大于枢轴； (3) 分别对两个子序列递归进行快速排序，直到 排序是计算机科学的重要内容，是计算机及相关 划分出的子序列的长度为 1。 专业的学生必须掌握的一类基础算法。快速排序以其 1.2 改进 优异的性能成为各种排序算法中的佼佼者。在日常讲 授、学习以及实现快速排序算法时，大都是以单线程 快速排序的平均性能非常优秀，但是在最坏情况 的模式进行。随着多核技术的发展与普及，对快速排 下，即序列已基本有序或是基本逆序时，快速排序的 序作多线程优化以进一步提高排序性能，可以使学生 性能会变得非常低[3] 。而且由于采用递归来进行排 更好地掌握多线程思想。Java 是当今的主流编程语言 序，当序列的长度较小时，频繁的递归操作也会影响 排序的性能。许多文献对快速排序的改进提出了建 之一，具有优秀的跨平台性。在 Java 平台上对快速 排序进行多线程优化，可适用于多种软硬件环境，应 议。Singleton 在文献[4]中使用“三点取中”方法， 用前景广阔。笔者首先基于 Java 平台对快速排序在 用序列中的头、尾和中点这三个关键字的中间值作为 小数据量情况下的优化做了测试，得到了一个可行的 枢轴，有效地避免了快速排序在最坏情况下的性能恶 优化方案，然后在 Java 中实现了归并方式的多线程 化。在内存使用上，快速排序需要使用额外的栈空间 快速排序，并在不同的软硬件环境下做了测试。测试 来进行递归操作。为减小栈的深度，在通过划分之后 结果表明，多线程排序能大幅提高排序的速度。 得到的子序列中，应优先对较小的子序列递归进行排 序[5] 。另外，快速排序的递归操作在序列长度较小时 1.1 算法概要 会影响排序的效率，应该使用其他非递归算法来处理 快速排序(Quicksort) 由Hoare 提出[1-2]，是现今最 小序列[6] 。 快的内部排序算法之一，其过程主要分为三个阶段： 对小序列进行处理时，使用直接插入排序是有效 (1) 在待排序的序列中找出一个枢轴； 的改进方法。此处通过测试来寻找从快速排序切换到 (2) 根据枢轴将待排序的序列划分成两个不相 插入排序的时机，为此设置一个阈值 M ，当快速排 交的子序列，其中一个子序列里的关键字全部