基數排序——多關鍵字排序（MSD/LSD)以及鍊式基數排序

排序

• 9.6 基數排序
• • 9.6.1 多關鍵字排序
  • 9.6.2 鍊式基數排序

9.6 基數排序

基數排序又被稱為桶排序。與前面介紹的幾種排序方法相比較，基數排序和它們有明顯的不同。前面所介紹的排序方法都是建立在對資料元素關鍵字進行比較的基礎上，是以可以稱為基于比較的排排序；而基數排序首先将待排序資料元素依次“配置設定”到不同的桶裡，然後再把各桶中的資料元素“收集”到一起。通過使用對多關鍵字進行排序的這種**“配置設定”和“收集”的方法，基數排序實作對單關鍵字**進行排序。

9.6.1 多關鍵字排序

1. 一般情況下，假定資料表中有n個資料元素(elem[0],elem[l],…… elem[n-1])。每個資料元素elem[i] (0<=i<=n-1)含有d個關鍵字(k1i，k2i，…，kdi)。如果對于序列中任意兩個資料元素 elem[j]和 elem[i] (0<=j<i<=n-1)都滿足：

   (k1i，k2i，…，kdi)<(k1j，k2j，…，kdj)

   則稱資料元素序列以關鍵字(k1，k2，…，kd)有序。在此，k1稱為最高位關鍵字，kd稱為最低位關鍵字。

2. 實作多關鍵字排序有兩種常用的方法:

   （1）最高位優先法 MSD (Most Significant Digit first)

   最高位優先法通常是一個遞歸的過程：

• 首先根據最高位關鍵字k1進行排序，按k1值的不同，将整個資料表分成若幹個子表，每個子表中的資料元素具有相同的關鍵字k1。
• 然後分别對每一個每個子表中的資料元素根據關鍵字(k2，…，kd)用最高位優先法進行排序。

• 如此遞歸，直到對關鍵字kd完成排序為止。

  （2）最低位優先法LSD (Last Significant Digit first)

  最低位優先法是:

• 首先依據最低位關鍵字kd對資料表中所有資料元素進行一趟排序;
• 然後依據次低位關鍵字kd-1對上一趟排序的結果再排序。
• 依次重複，直到按關鍵字k1完成最後一趟排序。

1. 兩種方法對比：

• LSD排序方式由關鍵字的最右邊位(低位)開始，先按關鍵字的最低位把所有元素配置設定到不同的“子桶”，然後依次把每個“子桶”中元素全部回收，完成一趟“配置設定”和“回收”:第2趟再按關鍵字的次低位把所有元素配置設定到不同的“子桶”，然後依次把每個“子桶”中元素全部回收……如此反複，在最後一趟“配置設定”“收集”完成後，所有資料元素就按其關鍵字的值從小到大排序好了。

• 而 MSD 則相反，由關鍵字的最左邊位(高位)開始，是由高位開始進行“配置設定”，但在“配置設定”之後并不把所有元素立即“收集”到一起，而是把每個“子桶”中的元素按照下一高位的值配置設定到“子子桶”中如此不斷“配置設定”，在完成最低位數的“配置設定”後，再把所有元素依次“收集”到一起。

  由此可見，最高位優先配置設定法的實作要比最低位優先配置設定法複雜。

使用LSD排序方法時，每一趟排序都是對整個資料表操作，且需采用穩定的排序方法。下面将介紹基于LSD方法的基數排序方法。

9.6.2 鍊式基數排序

1. LSD排序方法是一種典型的基數排序，它利用“配置設定”和“收集”這兩種運算實作多關鍵字排序。在這種方法中，把關鍵字k看成是一個d元組：(k1，k2，…，kd)。其中的每一個分量可以看成是一個單關鍵字，假設分量kj(1<=j<=d)有radix種取值，則稱radix 為基數。

• 例如，關鍵字984可以看成是一個三元組(9，8，4)，位數d=3，每一位可以取0,1.…, 9，這10種值，是以其基數radix=10。

1. 用LSD方法排序對d元組中的每一個分量kj，①把資料表中的所有資料元素按kj的取值先“配置設定”到radix個隊列(桶)中去，

   ②然後再按各隊列的順序，依把資料元素從隊列中“收集”起來，這樣所有資料元素按kj取值排序完成。

   ③如果對資料表中所有資料元素按關鍵字k(k1，k2，…，kd)，依次對各分量kj (j=d,d-1,…,1)分别用這種“配置設定”、“收集"的運算逐趟進行排序，在最後一趟“配置設定”、“收集”完成後，所有資料元素就按其關鍵字的值從小到大排序好了。

2. 在上述基數排序中，各個隊列可以考慮采用連結清單存儲結構，配置設定到同一隊列的關鍵字通過指針連結起來。

   一共有 radix個隊列，每一個隊列設定兩個隊列指針：

• 一個訓示隊頭，記為f[ i ]（0<=i<radix)；
• 另一個指向隊尾，記為e[ i ]（0<=i<radix)。
• 同時為了有效地存儲和重排，資料以靜态連結清單作為它的存儲結構。

  

1. 代碼實作

template<class ElemType> void RaxidSort(Node<ElemType> elem[],const int d,const int radix)
{
    int e[radix],f[radix],p,i,j,k,power;
    for(i=0; i<d; i++) //做d趟配置設定、收集
    {
        for(j=0; j<radix; j++)
            f[j]=0;//初始化各隊列配置設定
        power=(int)pow((double)radix,i);
        p=elem[0].next;//初始化連結清單搜尋指針
        while(p!=-1)//逐個元素配置設定
        {
            k=(elem[p].data/power)%radix;//取目前資料元素關鍵字的第i位
            if(f[k]==0)
                f[k]=p;//原連結清單為空時，資料元素入隊首
            else//原連結清單非空時，資料元素入隊尾
                elem[e[k]].next=p;
            e[k]=p;//修改鍊尾指針
            p=elem[p].next;//取連結清單中下一個節點
        }
        j=0;//開始資料收集
        while(f[j]==0)//跳過空隊列
            j++;
        elem[0].next=f[j];
        p=e[j];
        for(k=j+1; k<radix; k++)
            if(f[k]!=0)//回收每個非空隊列鍊入
            {
                elem[p].next=f[k];
                p=e[k];
            }
        elem[p].next=-1;
    }
}
           

1. 對于有n個資料元索的連結清單，若每個關鍵字有d位，算法需要重複執行d趟“配置設定”與“收集”。

   ①每趟進行**“配置設定”的循環需要執行n次**，把n個資料元素配置設定到radix個隊列中去；進行**“收集”的循環需要執行radix次**，把radix 個隊列中的資料元素收集起來按順序連結。是以總的時間複雜度為 O(d(n+radix)。

   ②算法所需要的附加存儲空間是為每個是資料元素結點增設的連結指針，及為每一個隊列設定的隊頭和隊尾指針，總共為n+2*radix。

   ③在基數排序中不需要移動資料元素，并且它是一種穩定的排序方法。