湖北第二师范学院学报
湖北第二師範學院學報
호북제이사범학원학보
JOURNAL OF HUBEI UNIVERSITY OF EDUCATION
2011年
8期
1-3
,共3页
快速排序%归并排序%二叉树%中序遍历
快速排序%歸併排序%二扠樹%中序遍歷
쾌속배서%귀병배서%이차수%중서편력
quick sort%merge sort%binary tree%in traverse sequence
快速排序算法可以解决高性能计算中理论算法在应用中出现的处理机个数问题。排序被认为占用了大量计算时间的一类问题。快速排序是一种典型的串行排序算法,它具有平均时间复杂度为O(nlogn)。如果利用并行算法来进行快速排序,时间复杂度仅只有O(2logn)。但是,当待排序的数据个数巨大时(如n〉10n),在并行算法中需要N台处理器,在实际应用中不具备可行性,但利用域划分,并把归并排序应用到快速排序中,一个可以用在待排序的数据个数巨大时的实用的并行算法。
快速排序算法可以解決高性能計算中理論算法在應用中齣現的處理機箇數問題。排序被認為佔用瞭大量計算時間的一類問題。快速排序是一種典型的串行排序算法,它具有平均時間複雜度為O(nlogn)。如果利用併行算法來進行快速排序,時間複雜度僅隻有O(2logn)。但是,噹待排序的數據箇數巨大時(如n〉10n),在併行算法中需要N檯處理器,在實際應用中不具備可行性,但利用域劃分,併把歸併排序應用到快速排序中,一箇可以用在待排序的數據箇數巨大時的實用的併行算法。
쾌속배서산법가이해결고성능계산중이론산법재응용중출현적처리궤개수문제。배서피인위점용료대량계산시간적일류문제。쾌속배서시일충전형적천행배서산법,타구유평균시간복잡도위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.