分割方式的多线程快速排序算法  

Multi-thread quicksort algorithm based on partitioning

作　　者：宋鸿陟[1] 傅熠[1] 张丽霞[1] 彭红星[1] 梁华坤[1] 

机构地区：[1]华南农业大学信息学院,广州510642

出　　处：《计算机应用》2010年第9期2374-2378,共5页journal of Computer Applications

基　　金：国家自然科学基金资助项目(60875045);教育部留学回国人员科研启动基金资助项目(2007年第31批次)

摘　　要：基于Java平台先对经典快速排序的改进方法作了介绍,通过测试得出了一个合适的经验阈值,改善了快速排序在小数据量情况下的低效问题。然后对快速排序作了多线程优化,并进行了单、多线程的对比测试,结果显示在多核主机上能有几倍的速度提升。最后对多线程快速排序算法进行了理论分析,得出了该算法速度的理论上限。Firstly, the improved method based on Java was introduced. A reasonable experimental threshold had been obtained, which improved the efficiency of quicksort when sorting a small dataset. Secondly, quicksort was optimized by using the multi-thread technology, and experiments were conducted to compare the performance of the single-thread and multi-thread algorithms. The results show that the multi-thread algorithm is several times faster than the single-thread one on multi-core computers. Finally, theoretical analysis was made on multi-thread quicksort algorithm, and the theoretical upper limit of the algorithm was obtained on multi-core computers.

关 键 词：分割 快速排序 多线程 效率上限 多核技术 

分 类 号：TP311.11[自动化与计算机技术—计算机软件与理论]