C#數(shù)據(jù)結(jié)構(gòu)與算法揭秘19

黃金屋1 2017-04-10

展開全文

這節(jié)，我們介紹基數(shù)排序和歸并排序。

一、基數(shù)排序

基數(shù)排序(Radix Sort)的設計思想與前面介紹的各種排序方法完全不同。前面介紹的排序方法主要是通過關鍵碼的比較和記錄的移動這兩種操作來實現(xiàn)排序的，而基數(shù)排序不需要進行關鍵碼的比較和記錄的移動。基數(shù)排序是一種借助于多關鍵碼排序的思想，是將單關鍵碼按基數(shù)分成多關鍵碼進行排序的方法，是一種分配排序。

下面用一個具體的例子來說明多關鍵碼排序的思想。
一副撲克牌有 52 張牌，可按花色和面值進行分類，其大小關系如下：
花色：梅花<方塊<紅心<黑心
面值：2<3<4<5<6<7<8<9<10<J<Q<K<A
在對這 52 張牌進行升序排序時，有兩種排序方法：
方法一：可以先按花色進行排序，將牌分為 4 組，分別是梅花組、方塊組、紅心組和黑心組，然后，再對這 4 個組的牌分別進行排序。最后，把 4 個組連接起來即可。
方法二：可以先按面值進行排序，將牌分為 13 組，分別是 2 號組、3 號組、4 號組、…、A 號組，再將這 13 組的牌按花色分成 4 組，最后，把這四組的牌連接起來即可。
設序列中有n個記錄，每個記錄包含d個關鍵碼{k1,k2,…,kd}，序列有序指的對序列中的任意兩個記錄ri和rj（1≤i≤j≤n），(ki1, ki2,…, kid)<( kj1, kj2,…, kjd) 其中，k1稱為最主位關鍵碼，kd稱為最次位關鍵碼。

其中，k1稱為最主位關鍵碼，kd稱為最次位關鍵碼。

多關鍵碼排序方法按照從最主位關鍵碼到最次位關鍵碼或從最次位關鍵碼到最主位關鍵碼的順序進行排序，分為兩種排序方法：
（1）最高位優(yōu)先法（MSD法）。先按k1排序，將序列分成若干子序列，每個子序列中的記錄具有相同的k1值；再按k2排序，將每個子序列分成更小的子序列；然后，對后面的關鍵碼繼續(xù)同樣的排序分成更小的子序列，直到按kd排序分組分成最小的子序列后，最后將各個子序列連接起來，便可得到一個有序的序列。前面介紹的撲克牌先按花色再按面值進行排序的方法就是MSD法。
（2）最次位優(yōu)先法（LSD法）。先按kd排序，將序列分成若干子序列，每個子序列中的記錄具有相同的kd值；再按kd-1排序，將每個子序列分成更小的子序列；然后，對后面的關鍵碼繼續(xù)同樣的排序分成更小的子序列，直到按k1排序分組分成最小的子序列后，最后將各個子序列連接起來，便可得到一個有序的序列。前面介紹的撲克牌先按面值再花色按進行排序的方法就是LSD法。

基數(shù)的源代碼如下：

//基數(shù)排序的方法
public int[] RadixSort(int[] ArrayToSort, int digit,int len)
        {
         
           // 從低位到高位的方法
            for (int k = 1; k <= digit; k++)
            {
                // 臨時的數(shù)組存儲里面的十進制的排序的結(jié)果
                int[] tmpArray = new int[ArrayToSort.Length];

                
                //臨時的數(shù)組存儲計數(shù)的結(jié)果
                int[] tmpCountingSortArray = new int[len];

                //基數(shù)的數(shù)組1            
                    for (int i = 0; i < ArrayToSort.Length; i++)
                {
                    //截取實際值   570-570/10*10
                    int tmpSplitDigit = ArrayToSort[i] / (int)Math.Pow(10, k - 1) - (ArrayToSort[i] / (int)Math.Pow(10, k)) * 10;
                    tmpCountingSortArray[tmpSplitDigit] += 1;
                }

                for (int m = 1; m < 10; m++)
                {
                    tmpCountingSortArray[m] += tmpCountingSortArray[m - 1];
                }

                //   輸出的結(jié)果
                for (int n = ArrayToSort.Length - 1; n >= 0; n--)
                {
                    int tmpSplitDigit = ArrayToSort[n] / (int)Math.Pow(10, k - 1) - (ArrayToSort[n] / (int)Math.Pow(10, k)) * 10;
                    tmpArray[tmpCountingSortArray[tmpSplitDigit] - 1] = ArrayToSort[n];
                    tmpCountingSortArray[tmpSplitDigit] -= 1;
                }

                //  拷貝排序的數(shù)組
                for (int p = 0; p < ArrayToSort.Length; p++)
                {
                    ArrayToSort[p] = tmpArray[p];
                }
            }

            return ArrayToSort;
        }
//雙層的循環(huán)    時間的復雜度是O(n2)

如圖所示：

基數(shù)排序是穩(wěn)定的排序，時間的復雜度是O(n2).

二、歸并排序

歸并排序(merge Sort)主要是二路歸并排序。二路歸并排序的基本思想是：將兩個有序表合并為一個有序表。
假設順序表 sqList 中的 n 個記錄為 n 個長度為1的有序表，從第1個有序表開始，把相鄰的兩個有序表兩兩進行合并成一個有序表，得到 n/2 個長度為2的有序表。如此重復，最后得到一個長度為 n 的有序表。
一趟二路歸并排序算法的實現(xiàn)如下所示，算法中記錄的比較代表記錄關鍵碼的比較，順序表中只存放了記錄的關鍵碼：

對于n個記錄的順序表，將這n個記錄看作葉子結(jié)點，若將兩兩歸并生成的子表看作它們的父結(jié)點，則歸并過程對應于由葉子結(jié)點向根結(jié)點生成一棵二叉樹的過程。所以，歸并趟數(shù)約等于二叉樹的高度減1，即log2n，每趟歸并排序記錄關鍵碼比較的次數(shù)都約為n/2，記錄移動的次數(shù)為2n（臨時順序表的記錄復制到原順序表中記錄的移動次數(shù)為n）。因此，二路歸并排序的時間復雜度為O （nlog2n）。
而二路歸并排序使用了n個臨時內(nèi)存單元存放記錄，所以，二路歸并排序算法的空間復雜度為O（n）。歸并排序，如圖所示：

一趟二路歸并排序算法的實現(xiàn)如下所示，算法中記錄的比較代表記錄關鍵碼的比較，順序表中只存放了記錄的關鍵碼，相應的源代碼如下：

public void Merge(SeqList<int> sqList, int len) 
   { 
        int m = 0；                 //臨時順序表的起始位置 
int l1 = 0;                 //第1個有序表的起始位置 
        int h1；                    //第1個有序表的結(jié)束位置 
int l2；                    //第2個有序表的起始位置 
int h2;                     //第2個有序表的結(jié)束位置 
        int i = 0; 
int j = 0;  
 
        //臨時表，用于臨時將兩個有序表合并為一個有序表 
        SeqList<int> tmp = new SeqList<int>(sqList.GetLength()); 
 
       //歸并處理 
        while (l1 + len < sqList.GetLength()) 
       {    
           l2 = l1 + len;           //第2個有序表的起始位置 
           h1 = l2 - 1;             //第1個有序表的結(jié)束位置 
 
          //第2個有序表的結(jié)束位置 
           h2 = (l2 + len - 1 < sqList.GetLength())  
? l2 + len - 1 : sqList.Last; 
 
           j = l2; 
           i = l1; 
 
           //兩個有序表中的記錄沒有排序完 
           while ((i<=h1) && (j<=h2)) 
           { 
                //第1個有序表記錄的關鍵碼小于第2個有序表記錄的關鍵碼 
                if (sqList[i] <= sqList[j])     
                { 
                    tmp[m++] = sqList[i++]; 
                } 
                //第2個有序表記錄的關鍵碼小于第1個有序表記錄的關鍵碼
else 
                { 
                    tmp[m++] = sqList[j++]; 
                } 
            } 
 
            //第1個有序表中還有記錄沒有排序完 
            while (i <= h1) 
            { 
                tmp[m++] = sqList[i++]; 
            } 
 
            //第2個有序表中還有記錄沒有排序完 
            while (j <= h2) 
            { 
                tmp[m++] = sqList[j++]; 
            } 
 
            l1 = h2 + 1; 
        } 
 
        i = l1; 
        //原順序表中還有記錄沒有排序完 
        while (i < sqList.GetLength()) 
        { 
            tmp[m++] = sqList[i++]; 
        } 
 
        //臨時順序表中的記錄復制到原順序表，使原順序表中的記錄有序 
       for (i = 0; i < sqList.GetLength(); ++i) 
        { 
            sqList[i] = tmp[i]; 
} 
} 
二路歸并排序算法的實現(xiàn)如下： 
public void MergeSort(SeqList<int> sqList) 
     { 
          int k = 1;     //歸并增量 
 
          while (k < sqList.GetLength()) 
          { 
               Merge(sqList, k); 
               k *= 2; 
           }
  }

對于n個記錄的順序表，將這n個記錄看作葉子結(jié)點，若將兩兩歸并生成的子表看作它們的父結(jié)點，則歸并過程對應于由葉子結(jié)點向根結(jié)點生成一棵二叉樹的過程。所以，歸并趟數(shù)約等于二叉樹的高度減1，即log2n，每趟歸并排序記錄關鍵碼比較的次數(shù)都約為n/2，記錄移動的次數(shù)為2n（臨時順序表的記錄復制到原順序表中記錄的移動次數(shù)為n）。因此，二路歸并排序的時間復雜度為O （nlog2n）。而二路歸并排序使用了n個臨時內(nèi)存單元存放記錄，所以，二路歸并排序算法的空間復雜度為O（n）。

C#數(shù)據(jù)結(jié)構(gòu)，就此結(jié)束了，這是我的一點總結(jié)。