【摘要】 排序是一个既有十分重要的理论意义又有广泛的实际应用价值的问题 ,其中 ,Multisets排序问题是指对只有k个不同关键字值的n个数据 (记录 )进行排序 ,0 <k <n 基于“中值的中值”思想和“筛选”原理 ,通过在递归过程中不断地“筛选”掉某些具有相同关键字值的数据 ,以及自适应地动态分配处理器以平衡计算负载的方法 ,设计一种确定的稳定的Multisets排序并行算法 在具有 p =n1-ε(0 <ε<1)个处理器的共享存储并行机器上 ,对于CREWPRAM模型 ,算法的时间复杂度为O((n/ p +pε)logk) ,获得最优执行代价O(nlogk) ;对于EREWPRAM模型 ,算法所需时间为O((n/ p+pε+logp)logk) ,当 plogp≤n时 ,其执行代价也是最优的 给出一种新的通过选择来实现并行排序的方法更多还原

【Abstract】 Sorting is a very interesting problem that has the important theoretical significance and widely applied value Sorting for multisets is to sort n numbers (records) that contain only k distinct key values, where 0<k<n In this paper, based on the idea of "median of medians" and principle of "filtering", a deterministic and stable parallel sorting algorithm for multisets is presented When the algorithm is executed recursively, some data with the same key values are filtered logically and the processors are assigned to the subtasks adaptively and dynamically in order to balance their computing loads For the shared memory parallel systems with p=n 1-ε processors, where 0< ε <1, the algorithm requires O((n/p+p ε) log k ) time and gets optimal O(n log k ) cost on CREW PRAM; its time complexity is O((n/p+p ε +log p )log k ), and its corresponding cost is also optimal when plogp≤n on EREW PRAM The main contribution of the paper is to present a new parallel sorting approach by applying selection technique更多还原