熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

排序 - 分配排序 - 基數排序

2013-11-15 15:39:42  來源: 數據結構 

  基數排序

  基數排序(Radix Sort)是對箱排序的改進和推廣

  單關鍵字和多關鍵字

  文件中任一記錄R[i]的關鍵字均由d個分量

  

構成

  若這d個分量中每個分量都是一個獨立的關鍵字則文件是多關鍵字的(如撲克牌有兩個關鍵字點數和花色);否則文件是單關鍵字

  的

  

(≤j

  多關鍵字中的每個關鍵字的取值范圍一般不同。如撲克牌的花色取值只有4種,而點數則有13種。單關鍵字中的每位一般取值范圍相

  同。

  2、基數

  設單關鍵字的每個分量的取值范圍均是:

  C 0 ≤k j ≤C rd-1 (0≤j

  可能的取值個數rd稱為基數。

  基數的選擇和關鍵字的分解因關鍵宇的類型而異:

  (1) 若關鍵字是十進制整數,則按個、十等位進行分解,基數rd=10,C 0 =0,C 9 =9,d為最長整數的位數;

  (2) 若關鍵字是小寫的英文字符串,則rd=26,C o ='a',C 25 ='z',d為字符串的最大長度。

  3、基數排序的基本思想

  基數排序的基本思想是:從低位到高位依次對K j (j=d-1,d-2,…,0)進行箱排序。在d趟箱排序中,所需的箱子數就是基數

  rd,這就是"基數排序"名稱的由來。

  4、基數排序的排序過程

  要排序的記錄關鍵字取值范圍是0到99之間的整數(36,5,16,98,95,47, 32,36,48)。對這些關鍵字進行基數排序的過程。

  5、基數排序的類型說明和算法描述

  要保證基數排序是正確的,就必須保證除第一趟外各趟箱排序是穩定的。相應的類型說明及算法描述【參見教材】。

  6、算法分析

  若排序文件不是以數組R形式給出,而是以單鏈表形式給出(此時稱為鏈式的基數排序),則可通過修改出隊和人隊函數使表示箱子

  的鏈隊列無須分配結點空間,而使用原鏈表的結點空間。人隊出隊操作亦無需移動記錄而僅需修改指針。雖然這樣一來節省了一定的

  時間和空間,但算法要復雜得多,且時空復雜度就其數量級而言並未得到改觀。 有關鏈式的基數排序可【閱讀參考書目[12]】。

  基數排序的時間是線性的(即O(n))。

  基數排序所需的輔助存儲空間為O(n+rd)。

  基數排序是穩定的。


From:http://tw.wingwit.com/Article/program/sjjg/201311/23764.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.