并行快速排序算法的实现

并行快速排序算法的实现

苏晓勤，王梦倩，王钢

天津商业大学 信息工程学院，天津 天津 300130

摘要：利用多核并行思想实现快速排序算法，分析了不同数据量、不同数量处理器对于排序效率的影响，并基于多组实验数据对实验结果进行了分析对比。由于划分进程及多核间通信需要时间，当参与快速排序的数据量大时，多核并行的排序所花费的时间少、效果好。

关键词：快速排序算法；多核并行思想；进程

一、引言

多核应用研究已成为最受关注的主题和最受瞩目的研究方向，多核的基础上并行计算得到了普遍的运用^[1]。多核并行编程充分利用多核心处理器的优异性能有效地提高运算速度^[2]。真对传统的排序算法—快速排序进行并行实现很有意义。

二、快速排序算法

快速排序是对冒泡排序的一种改进，其基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序的平均时间复杂度为 。当整个序列基本有序或倒序时快速排序蜕化成冒泡排序，最坏情况的时间复杂度为 。

三、并行快速排序算法

ForkJoin框架是Java7提供的一个并行计算的框架，适合分治思想的排序算法。它主要是用于把一个大任务拆分为若干个小任务，然后把若干个小任务运行的结果再汇总为大任务的结果。并行快速排序就是利用该框架，将待排序数组分割成若干短数组，对每个短数组进行串行排序，形成局部有序的数组，然后进行两两合并得到最后的有序数组。具体实现过程如下：

（1）生成随机的数据用于排序。

（2）调用ForkJoinPool对排序任务进行任务划分。

（3）运用快速排序的思想将已经划分好的小任务进行排序。

（4）调用各个小任务的排序结果进行汇总排序。

（5）得出最终结果。

四、实验结果及对比

图1是当排序的数据为10个随机生成数时，并行快速排序所花费时间的结果。图中可以得出参与排序的数据量不够大时，并行快速排序算法在进程的创建与通信上花费了很多时间，效率低。

图1 随机生成10个数时并行快速排序的运行时间

实验数据采用随机产生数分别计算花费在多核多线程和单核排序的时间，结果取10次运行结果的平均值，实验结果如图2所示。

图2 两种快速排序算法的运行时间对比图

五、结束语

实验结果表明，当数据量较小时单核排序进行排序效果好，而当数据量较大的时，多核多线程并行快速排序算法具有更大优势，随着参与排序数据量的增加，并行快速排序算法的效率更高。

参考文献：

[1]钱晓捷,李秀芳. 基于多核多线程的排序算法优化和实现[J].微电子学与计算机,2011(01):116-119.

[2]陈国良. 并行计算一结构.算法.编程[M].高等教育出版社,2003

[3]张天阳,陈华. 基于4种并行模式的快速排序算法[J].成都信息工程大学学报,2018(02):13-17

基金项目：天津商业大学青年基金项目（项目编号：090110）。

作者简介：苏晓勤（1978-），女，河北定州人，天津商业大学讲师，研究方向：人工智能；

王梦倩（1975-），女，山东青岛人，天津商业大学讲师，研究方向：计算机应用；

王钢（1973-），男，天津人，天津商业大学讲师，研究方向：计算机应用。