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