人妖在线一区,国产日韩欧美一区二区综合在线,国产啪精品视频网站免费,欧美内射深插日本少妇

新聞動(dòng)態(tài)

python之基數(shù)排序的實(shí)現(xiàn)

發(fā)布日期:2022-02-21 16:40 | 文章來(lái)源:CSDN

算法思想

        插入\交換\選擇\歸并類的排序算法都需要通過(guò)比較關(guān)鍵字的大小來(lái)完成排序.因?yàn)榇嬖趦蓛杀容^所以這一類的排序方法在最好情況下能達(dá)到的復(fù)雜度是O(n*logn),如快速排序\堆排序\歸并排序.在一般情況下和最壞情況下復(fù)雜度更是達(dá)到O(n**2).

        為了降低復(fù)雜度,就有牛人想出了分配收集排序方法,稍后分析它的時(shí)間復(fù)雜度能到達(dá)O(n),

而基數(shù)排序就是一種典型的搜集分配收集排序方法.基數(shù)排序時(shí)一種借助于多關(guān)鍵字排序的思想對(duì)單關(guān)鍵字排序的方法.其基本思想是通過(guò)對(duì)排序記錄進(jìn)行若干趟(有幾個(gè)關(guān)鍵字就幾趟)"分配"與"收集"來(lái)實(shí)現(xiàn)排序.

        如:

       1. 對(duì)整數(shù)排序,建立編號(hào)0-9(10進(jìn)制的基數(shù))10個(gè)桶,用于裝對(duì)應(yīng)位為編號(hào)的記錄.先將待排序序列分配按'個(gè)位'數(shù)字分配到10各桶中,然后將桶按從小到大的順序串接起來(lái).

        2.將上一步的結(jié)果再按'十位''數(shù)字分配到10各桶中,然后將桶按從小到大的順序串接起來(lái).

        3. 將上一步的結(jié)果再按'百位''數(shù)字分配到10各桶中,然后將桶按從小到大的順序串接起來(lái).

        4.如果還有千位\萬(wàn)位.重復(fù)以上步驟,直到完成最高位的分配與收集,排序結(jié)束.

動(dòng)圖示例:(轉(zhuǎn)自菜鳥(niǎo)教程:1.10 基數(shù)排序 | 菜鳥(niǎo)教程 (runoob.com))

 

算法實(shí)現(xiàn)

1.本實(shí)現(xiàn)借助隊(duì)列的數(shù)據(jù)結(jié)構(gòu),所以先來(lái)定義一個(gè)隊(duì)列

# Bradley N. Miller, David L. Ranum
# Introduction to Data Structures and Algorithms in Python
# Copyright 2005
# 
#queue.py
 
class Queue:
 def __init__(self):
  self.items = []
 
 def isEmpty(self):
  return self.items == []
 
 def enqueue(self, item):
  self.items.insert(0,item)
 
 def dequeue(self):
  return self.items.pop()
 
 def size(self):
  return len(self.items)

2.處理輸入數(shù)據(jù)

將一個(gè)列表作為輸入,將每一個(gè)記錄處理為具有相同位數(shù)的字符串(用字符串類型時(shí)為了方便處理)

def inDataProcess(lis):
 max_lengh = max([len(lis[i]) for i in range(len(lis))])  # 查詢記錄中最長(zhǎng)的字符串
 return [x.zfill(max_lengh) for x in lis]  # 將每一個(gè)記錄都通過(guò)添加前導(dǎo)0的方式轉(zhuǎn)化為一樣的長(zhǎng)度

3.基數(shù)排序主函數(shù)

def radixSort(seq:list):
 source_data = inDataProcess(seq)  # 輸入處理
 res = []  # 用于保存結(jié)果列表
 big_queue = Queue()  # 用于轉(zhuǎn)化的隊(duì)列
 for ele in source_data:
  big_queue.enqueue(ele)
 
 for i in range(len(source_data[0])-1,-1,-1):
  buckets = []  # 用于保存每一趟的10各基數(shù)桶
  for num  in range(10):  # 建立10個(gè)基數(shù)桶
bucket = Queue()
buckets.append(bucket)
  # 在基數(shù)桶中插入數(shù)據(jù)
  while not big_queue.isEmpty():
currentEle = big_queue.dequeue()  # 大隊(duì)列中出隊(duì)一個(gè)元素
index = int(currentEle[i])  # 根據(jù)元素對(duì)應(yīng)位上的值添加進(jìn)對(duì)應(yīng)的基數(shù)桶中
buckets[index].enqueue(currentEle)
 
  # 把基數(shù)桶串聯(lián)起來(lái)
  new_big_queue = Queue()
  for bucket in buckets:
while not bucket.isEmpty():
 out = bucket.dequeue()
 new_big_queue.enqueue(out)
 # print(new_big_queue.size())
  # 修改big_queue
  big_queue = new_big_queue
 # 將大隊(duì)列中的元素保存到結(jié)果列表中
 while not big_queue.isEmpty():
  res.append(big_queue.dequeue().lstrip('0'))  # 利用lstrip('0')去掉前導(dǎo)0
 return res

4.測(cè)試及結(jié)果

if __name__ == '__main__':
 
 lis = [20,101,39,431,58,600,8,4,999,634,157,199,208,138,389,691,400,932,856,843,401,923]
 lis = [str(i) for i in lis]
 print(radixSort(lis))
 ''' 結(jié)果>>>['4', '8', '20', '39', '58', '101', '138', '157', '199', '208', '389', '400', '401', '431', '600', '634', '691',
 '843', '856', '923', '932', '999']'''

算法分析

1)時(shí)間復(fù)雜度
對(duì)于n個(gè)記錄(假設(shè)每個(gè)記錄含d個(gè)關(guān)鍵字,每個(gè)關(guān)鍵字的取值范圍為rd個(gè)值)進(jìn)行鏈?zhǔn)交鶖?shù)排序時(shí),每一趟分配的時(shí)間復(fù)雜度為O(n),每一趟收集的時(shí)間復(fù)雜度為O(rd),整個(gè)排序需進(jìn)行d趟分配和收集,所以時(shí)間復(fù)雜度為O(d(n+rd))。
(2)空間復(fù)雜度
所需輔助空間為2rd個(gè)隊(duì)列指針,另外由于需用鏈表做存儲(chǔ)結(jié)構(gòu),則相對(duì)于其他以順序結(jié)構(gòu)存儲(chǔ)記錄的排序方法而言,還增加了n個(gè)指針域的空間,所以空間復(fù)雜度為O(n+rd)。

算法的特征

(1)是穩(wěn)定排序。
(2)可用于鏈?zhǔn)浇Y(jié)構(gòu),也可用于順序結(jié)構(gòu)。
(3)時(shí)間復(fù)雜度可以突破基于關(guān)鍵字比較一類方法的下界O(nlog2n),達(dá)到O(n)。
(4)基數(shù)排序使用條件有嚴(yán)格的要求:需要知道各級(jí)關(guān)鍵字的主次關(guān)系和各級(jí)關(guān)鍵字的取值范圍。


ref: 

1.嚴(yán)蔚敏等<<數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(第二版)>>

2.Bradley N. Miller, David L. Ranum <<Introduction to Data Structures and Algorithms in Python>>

到此這篇關(guān)于python之基數(shù)排序的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)python之基數(shù)排序內(nèi)容請(qǐng)搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站!

香港服務(wù)器租用

版權(quán)聲明:本站文章來(lái)源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有,歡迎引用、轉(zhuǎn)載,請(qǐng)保持原文完整并注明來(lái)源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站,禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像,否則將依法追究法律責(zé)任。本站部分內(nèi)容來(lái)源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來(lái),僅供學(xué)習(xí)參考,不代表本站立場(chǎng),如有內(nèi)容涉嫌侵權(quán),請(qǐng)聯(lián)系alex-e#qq.com處理。

相關(guān)文章

實(shí)時(shí)開(kāi)通

自選配置、實(shí)時(shí)開(kāi)通

免備案

全球線路精選!

全天候客戶服務(wù)

7x24全年不間斷在線

專屬顧問(wèn)服務(wù)

1對(duì)1客戶咨詢顧問(wèn)

在線
客服

在線客服:7*24小時(shí)在線

客服
熱線

400-630-3752
7*24小時(shí)客服服務(wù)熱線

關(guān)注
微信

關(guān)注官方微信
頂部