快排序并行算法的N值問題
2013-09-30 06:39:40楊艷
中國信息化·學(xué)術(shù)版 2013年6期
楊艷
[摘要]本文在一個PRAMCRCW（paralled random accessmachin concurrent read concurrent write）上詳細(xì)的介紹了并行快速排序算法，并在此基礎(chǔ)上提出了利用歸并排序和快速排序相結(jié)合的新算法，解決了快速排序并行算法里處理器個數(shù)的N值問題。這個算法將長度為n的待排序數(shù)據(jù)利用域劃分分成長度為p的子序列，在時(shí)間復(fù)雜度為O（2logp+logk）情況下得到有序序列。
[關(guān)鍵詞]并行算法；快速排序算法；歸并排序；二叉樹；中序遍歷
[中圖分類號]F224-39 [文獻(xiàn)標(biāo)識碼]A [文章編號]1672-5158（2013）06-0121-02
