归并方式的多线程快速排序算法  

A Multi-thread Quicksort Algorithm Based on Merging

作　　者：宋鸿陟[1] 傅熠[1] 肖磊[1] 张丽霞[1] 邓展鸿[1] 

机构地区：[1]华南农业大学信息学院人机交互研究中心,广东广州510642

出　　处：《计算机教育》2010年第8期149-152,共4页Computer Education

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

摘　　要：本文基于Java平台针对经典快速排序提出改进方案,使用归并的思想对快速排序作了多线程优化,并对单、多线程下的快速排序进行了对比测试和分析。结果表明,通过多线程优化,快速排序在双核主机上对5千万个随机整型数据进行排序的速度是单线程的1.6倍,说明了该优化方法的有效性。该方法思路直观、容易理解,宜作为多核技术教学案例。This article introduces the classical Quicksort algorithm and its optimization methods,then presents a general strategy to further improve its performance by applying the multi-thread technique in the manner of Mergesort.We implemented both of the single and multi-thread algorithms in Java.Through the comparison tests and analysis of single and multi-thread Quicksort,we found the speed of multi-thread Quicksort is 1.6 times faster than the single-thread one when sorting a random set of 50,000,000 integers in a dual-core host.This strategy is intuitive and intelligible,and it is believed to be a good example for teaching students multi-core technology in class.

关 键 词：快速排序 归并 多线程 

分 类 号：G642[文化科学—高等教育学]