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.

Key words: partition, quicksort, multi-thread, performance limit, multi-core technology

摘要： 基于Java平台先对经典快速排序的改进方法作了介绍，通过测试得出了一个合适的经验阈值，改善了快速排序在小数据量情况下的低效问题。然后对快速排序作了多线程优化，并进行了单、多线程的对比测试，结果显示在多核主机上能有几倍的速度提升。最后对多线程快速排序算法进行了理论分析，得出了该算法速度的理论上限。

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