| 分割方式的多线程快速排序算法 |
| |
| 引用本文： | 宋鸿陟,傅熠,张丽霞,彭红星,梁华坤. 分割方式的多线程快速排序算法[J]. 计算机应用, 2010, 30(9): 2374-2378 |
| |
| 作者姓名： | 宋鸿陟 傅熠 张丽霞 彭红星 梁华坤 |
| |
| 作者单位： | 1. 华南农业大学2. 华南农业大学信息学院3. |
| |
| 基金项目： | 国家自然科学基金资助项目，教育部留学回国人员科研启动基金资助项目 |
| |
| 摘 要： | 基于Java平台先对经典快速排序的改进方法作了介绍，通过测试得出了一个合适的经验阈值，改善了快速排序在小数据量情况下的低效问题。然后对快速排序作了多线程优化，并进行了单、多线程的对比测试，结果显示在多核主机上能有几倍的速度提升。最后对多线程快速排序算法进行了理论分析，得出了该算法速度的理论上限。
|
| 关 键 词： | 分割 快速排序 多线程 效率上限 多核技术 |
| 收稿时间： | 2010-03-10 |
| 修稿时间： | 2010-05-02 |
Multi-thread quicksort algorithm based on partitioning |
| |
| SONG Hong-zhi,FU Yi,ZHANG Li-xia,PENG Hong-xing,LIANG Hua-kun. Multi-thread quicksort algorithm based on partitioning[J]. Journal of Computer Applications, 2010, 30(9): 2374-2378 |
| |
| Authors: | SONG Hong-zhi FU Yi ZHANG Li-xia PENG Hong-xing LIANG Hua-kun |
| |
| Abstract: | 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. |
| |
| Keywords: | partition quicksort multi-thread performance limit multi-core technology |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用》浏览原始摘要信息 |
|
点击此处可从《计算机应用》下载全文 |
|
