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

归并方式的多线程快速排序算法
　　摘要：本文基于Java平台针对经典快速排序提出改进方案，使用归并的思想对快速排序作了多线程优化，并对单、多线程下的快速排序进行了对比测试和分析。结果表明，通过多线程优化，，说明了该优化方法的有效性。该方法思路直观、容易理解，宜作为多核技术教学案例。
　　关键词：快速排序；归并；多线程
　　文章编号：1672-5913(2010)08-0149-04
　　中图分类号：G642
　　文献标识码：A
　　
　　1　快速排序
　　
　　排序是计算机科学的重要内容，是计算机及相关专业的学生必须掌握的一类基础算法。快速排序以其优异的性能成为各种排序算法中的佼佼者。在日常讲授、学习以及实现快速排序算法时，大都是以单线程的模式进行。随着多核技术的发展与普及，对快速排序作多线程优化以进一步提高排序性能，可以使学生更好地掌握多线程思想。Java是当今的主流编程语言之一，具有优秀的跨平台性。在Java平台上对快速排序进行多线程优化，可适用于多种软硬件环境，应用前景广阔。笔者首先基于Java平台对快速排序在小数据量情况下的优化做了测试，得到了一个可行的优化方案，然后在Java中实现了归并方式的多线程快速排序，并在不同的软硬件环境下做了测试。测试结果表明，多线程排序能大幅提高排序的速度。
　　
　　
　　1，1算法概要
　　快速排序(Quicksort)由Hoare提出，是现今最快的内部排序算法之一，其过程主要分为三个阶段：
　　(1)在待排序的序列中找出一个枢轴；
　　(2)根据枢轴将待排序的序列划分成两个不相交的子序列，其中一个子序列里的关键字全部不小于枢轴，另一个子序列里的关键字全部不大于枢轴；
　　(3)分别对两个子序列递归进行快速排序，直到划分出的子序列的长度为1。
　　
　　1，2改进
　　快速排序的平均性能非常优秀，但是在最坏情况下，即序列已基本有序或是基本逆序时，快速排序的性能会变得非常低。而且由于采用递归来进行排序，当序列的长度较小时，频繁的递归操作也会影响排序的性能。许多文献对快速排序的改进提出了建议。Singleton在文献中使用
“三点取中”方法，用序列中的头、尾和中点这三个关键字的中间值作为枢轴，有效地避免了快速排序在最坏情况下的性能恶化。在内存使用上，快速排序需要使用额外的栈空间来进行递归操作。为减小栈的深度，在通过划分之后得到的子序列中，应优先对较小的子序列递归进行排序。另外，快速排序的递归操作在序列长度较小时会影响排序的效率，应该使用其他非递归算法来处理小序列。
　　
　　对小序列进行处理时，使用直接插入排序是有效的改进方法。此处通过测试来寻找从快速排序切换到插入排序的时机，为此设置一个阈值M，当快速排序过程中划分出的子序列的长度小于或等于M时，不再递归调用快速排序而使用直接插入排序，以避免对小序列排序时的频繁递归。这里M值的选取非常重要，会对排序的速度产生较大的影响。因为当M值偏小时，相当于没有做改进；如果M值偏大，则无法体现快速排序的优势。M值的选取与计算机软硬件因素相关，这里对M选取了一组值f4，8，16，32，64，128，256}