先簡單說一下給的A，B，C 三種算法(見上面引用的那篇博客)，A算法將耗時的平方和開平方計算放到比較函數中，導致Array.Sort 時，每次亮亮比較都要執行平方和開平方計算，其平均算法復雜度為 O(nlog2n) 。 而B 將平方和開平方計算提取出來，算法復雜度降低到 O(n) ，這也就是為什么B比A效率要高很多的緣故。C 和 B 相比，將平方函數替換成了 x*x ，由于少了遠程函數調用和Pow函數本身的開銷，效率有提高了不少。我在C的基礎上編寫了D算法，D算法采用并行計算技術，在我的雙核筆記本電腦上數據量比較大的情況下，其排序效率較C要提高30%左右。

　　下面重點介紹這個并行排序算法。算法思路其實很簡單，就是將要排序的數組按照處理器數量等分成若干段，然后用和處理器數量等同的線程并行對各個小段進行排序，排序結束和，再在單一線程中對這若干個已經排序的小段進行歸并排序，最后輸出完整的排序結果。考試大考慮到和.Net 2.0 兼容，沒有用微軟提供的并行庫，而是用多線程來實現。

　　下面是測試結果：

　　n A B C D

　　32768 0.7345 0.04122 0.0216 0.0254

　　65535 1.5464 0.08863 0.05139 0.05149

　　131072 3.2706 0.1858 0.118 0.108

　　262144 6.8423 0.4056 0.29586 0.21849

　　524288 15.0342 0.9689 0.7318 0.4906

　　1048576 31.6312 1.9978 1.4646 1.074

　　2097152 66.9134 4.1763 3.0828 2.3095

　　從測試結果上看，當要排序的數組長度較短時，并行排序的效率甚至還沒有不進行并行排序高，這主要是多線程的開銷造成的。當數組長度增大到25萬以上時，并行排序的優勢開始體現出來，隨著數組長度的增長，排序時間最后基本穩定在但線程排序時間的 74% 左右，其中并行排序的消耗大概在50%左右，歸并排序的消耗在 14%左右。由此也可以推斷，如果在4CPU的機器上，其排序時間最多可以減少到單線程的 14 + 25 = 39%。8 CPU 為 14 + 12.5 = 26.5%。

　　目前這個算法在歸并算法上可能還有提高的余地，如果哪位高手能夠進一步提高這個算法，不妨貼出來一起交流交流。

　　下面分別給出并行排序和歸并排序的代碼：

　　并行排序類 ParallelSort

　　Paralletsort 類是一個通用的泛型，調用起來非常簡單，下面給一個簡單的int型數組的排序示例：

　　class IntComparer : IComparer < int >

　　{

　　IComparer Members #region IComparer Members

　　public int Compare( int x, int y)

　　{

　　return x.CompareTo(y);

　　}

　　#endregion

　　}

　　public void SortInt( int [] array)

　　{

　　Sort.ParallelSort < int > parallelSort = new Sort.ParallelSort < int > ();

　　parallelSort.Sort(array, new IntComparer());

　　}

　　軟考軟件設計師歷年真題匯總(2007年-2010年)

　　2011年軟件水平考試軟件設計師知識點總結

　　2011軟件水平考試軟件設計師輔導資料匯總