排序網絡算法是基于比較網絡模型，可以同時執行多個比較操作，和串行計算（隨機存取計算機RAM）機制不一樣。首先要介紹下比較網絡。比較網絡由線路和比較器構成。一條線路把一個值從一處傳輸到另一處，把比較器的輸入端和輸出端相連。
假定比較網絡含n條輸入線a1,a2,…,an，以及n條輸出線b1,b2,…,bn，需要排序的值通過輸入線進入網絡，由網絡計算出的結果通過輸出線輸出。算法導論中給出的案例很清晰地表達了比較網絡的概念和特點，由線路互聯的一組比較器組成。關注兩個特點：
第一：只有當同時有兩個輸入時，比較器才能產生輸出值。簡單理解，比較器之比較在于有兩個值的比較，一個值輸入不構成比較意義；
第二：一個比較網絡的深度是它的輸出線路的最大深度，就是比較器的深度；比較器的深度由最深的線路來決定，如果一個比較器有兩條深度分別為dx和dy的輸入線路，則其輸出線路深度為max(dx,dy)+1；第一個特點也決定了比較器的深度，因為只有輸入兩個值才算一個深度的開始。
綜上，定義排序網絡為：對每個輸入序列，其輸出序列均為單調遞增（即b1≤b2≤…≤bn）的一種比較網絡。輸入n個值（n條線路）經過比較器（深度不同）的比較最后輸出n個值正排序。比較器其實就是簡單的min和max兩個值選擇。
1）0-1原理
0-1原理推定認為：如果對于屬于集合{0,1}的每個輸入值，排序網絡都能正確運行，則對任意輸入值，它也能爭取而運行（輸入值可以是整數、實數或者任意線性排序的值的集合）。這樣在構造排序網絡時，可以專注在0和1組成的輸入序列上設計比較器。這個原理目的是簡化輸入值，而通過0和1來設計比較網絡的線路和比較器，只要0和1可運行，那么其他任意值的序列也都可以運行。
0-1原理的證明依賴單調遞增函數。如果比較網絡把輸入序列a=<a1,a2,…,an>轉化為輸出序列b=<b1,b2,…,bn>，則對任意單調遞增函數f，該網絡把輸入序列f(a)=<f(a1),f(a2),…,f(an)>轉化為輸出序列f(b)=<f(b1),f(b2),…,f(bn)>。
這個可以這樣理解，就是對輸入序列a施以f(a)單調遞增函數，比較網絡（線路和比較器）能夠使序列a輸出序列b，那么該比較網絡同樣可以使輸入序列f(a)輸出序列f(b)。
這就為0-1原理奠定了基礎，只要證明比較網絡可以運行于0和1的輸入，那么設計一個單調遞增函數，0和1是因變量，其自變量自然也可以通過同樣比較網絡來排序。
如果一個具有n個輸入的比較網絡能夠對所有可能存在的2n個0和1組成的序列進行正確的排序，則對所有任意數組成的序列，該比較網絡也可能對其正確排序。
0-1原理證明用到了單調遞增函數概念，同時采用數學歸納法和反證法來證明。這也給出了一個很重要的思想，那就是對現實問題的解決，在構建數學模型時，可以簡單到0-1，然后再推廣到復雜數。
2）雙調排序網絡
基于0-1原理構造有效的排序網絡，首先是構造能對任意雙調序列進行排序的比較網絡，再合并網絡。
那么什么是雙調序列呢？雙調序列是指序列要么單調遞增后再單調遞減，或者循環移動成為先單調遞增后再單調遞減。考慮邊界情況，任何1個或2個的數構成的序列都是雙調的，雙調0-1序列的結構是0i1k0j或1i0k1j，其中i、j、k≥0，自然單調遞增或單調遞減的序列也是單調的。
怎么理解雙調序列呢？比喻為山巒起伏，一山比一山高再一山比一山低，中間是單調性的。基于0-1原理，只要我們所構造的雙調排序程序能對0和1的雙調序列進行排序的比較網絡，這個比較網絡也適用于任何數值。
雙調排序通過迭代半清潔器來實現。半清潔器就是深度為1的比較網絡，輸入雙調序列，進行深度1次的比較器，輸出雙調序列，而“半”的意思是指比較器的兩個輸入值是由輸入線i和輸入線i+n/2進行比較。雙調序列經過半清潔器輸出的雙調序列結果是：較小的值位于輸出的上半部，較大的值位于輸出的下半部，并且兩部分的序列仍然是雙調的。為此得出如下結論：
如果半清潔器的輸入是一個由0和1組成的雙調序列，則其輸出滿足如下性質，輸出的上半部分與下半部分都是雙調的，上半部分輸出的每一個元素至少與下半部分輸出的每個元素一樣小，并且兩部分中至少有一個部分是清潔的。
輸入雙調序列，然后遞歸連接半清潔器，就可以建立一個雙調排序器，實現對雙調序列排序的比較網絡。
3）合并網絡
合并網絡，能夠把兩個已排序的輸入序列合并為一個有序的輸出序列的網絡。基于雙調排序網絡思想，對已知的兩個有序序列進行連接（第二個序列順序顛倒），所得的序列是雙調序列，再利用雙調排序器就能完成兩個有序序列的合并。
4）排序網絡
基于0-1原理、雙調排序網絡、合并網絡，我們可以構造一個輸入任意序列進行排序的比較排序網絡。思想很簡單：第一步開展最基礎的2個元素的兩兩比較，這個用普通的比較器就可以實現，輸出長度為2的有序序列；第二步對長度為2的有序序列進行兩兩合并，這個用合并網絡排序（基于雙調排序器，先連接序列構造雙調序列）實現，輸出長度為4的有序序列；第三步對長度為4的有序序列進行合并網絡，直到lgn次。算法上，可以在O(lg2n)內并行地對n個數進行排序。
排序網絡可以并行地進行排序，然后再組合各并行排序結果，適合分布式場景的排序需求。

總結

以上是生活随笔為你收集整理的算法导论之排序网络的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。