并行计算中快速排序算法的改进  

Impovement on Fast Scheduling in Parallel Computing

作　　者：李跃新[1] 周四维[2] 

机构地区：[1]湖北大学数学与计算机科学学院,武汉430064 [2]湖北大学知行学院,武汉430046

出　　处：《湖北第二师范学院学报》2011年第8期1-3,共3页Journal of Hubei University of Education

摘　　要：快速排序算法可以解决高性能计算中理论算法在应用中出现的处理机个数问题。排序被认为占用了大量计算时间的一类问题。快速排序是一种典型的串行排序算法,它具有平均时间复杂度为O(nlogn)。如果利用并行算法来进行快速排序,时间复杂度仅只有O(2logn)。但是,当待排序的数据个数巨大时(如n>10n),在并行算法中需要N台处理器,在实际应用中不具备可行性,但利用域划分,并把归并排序应用到快速排序中,一个可以用在待排序的数据个数巨大时的实用的并行算法。This thesis is mainly about the development of high-performance of computering and problem solving,and an example（quick sort） about the problems in parallel computing.Sorting by that takes up a lot of time in the class.Quick sort is a kind of typical serial sorting algorithm,and its average time complexity is O（nlogn）.With parallel algorithms for quick sort,time complexity only O（2logn）.However,when the number of huge sorting data（such as n10n）,in parallel algorithm needs n set processor,in actual application of feasibility,as does not have the parallel processing technology and the development of our quick sort of further research,this paper puts forward a new kind of parallel scheduling algorithm by using the domain,and-the merge sort of thought to a parallel algorithms can be realized.

关 键 词：快速排序 归并排序 二叉树 中序遍历 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]