黄志波，赵　晴，孙少乙

(华北计算机系统工程研究所，北京 100083)



基于Java的多线程快速排序设计与优化

黄志波，赵晴，孙少乙

(华北计算机系统工程研究所，北京 100083)

为实现多线程快速排序，提出基于Fork/Join框架的多线程快速排序，同时对排序算法进行优化。该算法主要用于大量数据需要进行排序处理的应用。

Fork/Join；多线程；快速排序；算法优化

引用格式：黄志波，赵晴，孙少乙. 基于Java的多线程快速排序设计与优化[J].微型机与应用，2016,35(16)：23-25，28.

0　引言

排序一直是程序开发中的一个重点，尤其在一些应用开发中经常用到，在搜索开发中也是重点研究对象。所以人们对排序的研究一直坚持不懈。在众多排序算法中，快速排序是一个表现极其优秀的算法。该算法于1962年由Tony Hoare首次提出[1]，它基于分治思想，使得排序性能得到极大的提升[2]。如今的电脑或者手机一般都是多核处理器，为了提高用户体验，应该充分利用其所拥有的硬件设备。本文主要讲述多线程下快速排序的设计与优化过程，对普通快速排序[3]、基于多线程的快速排序以及基于Fork/Join的多线程排序进行了比较。

1　单线程快速排序

快速排序是基于比较的一种排序算法，而基于比较的排序算法的最佳性能为O(nlgn)。快速排序的运行时间与数据划分是否对称有关，且与选择了哪一个元素作为划分基准有关[4]。在信息论里面，N个未排序的数字，共有N！种排法，但是只有一种是想要的(譬如递增或者递减)。也就是说，排序问题的可能性有N！种，而任何基于比较的排序基本操作单元都是“比较a和b”，而这个比较一般是有两个结果，这样恰好可将剩下来的排序减少为N!/2种。……