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

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

　　下面是測試結(jié)果：

　　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

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

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

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

　　并行排序類 ParallelSort

　　Paralletsort 類是一個(gè)通用的泛型，調(diào)用起來非常簡單，下面給一個(gè)簡單的int型數(shù)組的排序示例：

　　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());

　　}

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

　　2011年軟件水平考試軟件設(shè)計(jì)師知識(shí)點(diǎn)總結(jié)

　　2011軟件水平考試軟件設(shè)計(jì)師輔導(dǎo)資料匯總