桶排序和計數(shù)排序
桶排序
在說計數(shù)排序之前需要先提一下桶排序，因為計數(shù)排序實際上可以被認為是一種特殊的桶排序。
桶排序浸卦，顧名思義该默，需要準備很多桶，比如在一次數(shù)學考試過后地啰，需要給同學們按成績高低排個序愁拭，學生人數(shù)是56，成績最低為0分亏吝，滿分為120岭埠。
我們就可以準備6個桶：A、B、C惜论、D许赃、E、F馆类，每個桶存放不同區(qū)段的成績混聊。
F桶：0~20
E桶：21~40
D桶：41~60
C桶：61~80
B桶：81~100
A桶：101~120
遍歷一遍數(shù)據(jù)將成績放入不同的桶里面之后，再對每個桶里面的數(shù)據(jù)進行快速排序乾巧，然后將排好序的數(shù)據(jù)按FEDCBA的順序合在一起句喜。
桶排序時間復雜度分析
- 遍歷一次，將數(shù)據(jù)放入對應的桶中卧抗，
- 假設數(shù)據(jù)分散比較均勻藤滥，被分到k個桶中，每個桶中數(shù)據(jù)大概是
- 每個桶內(nèi)的快速排序為
- 綜合一下社裆，桶排序的時間復雜度是
- 當k無限趨近與n的時候拙绊，
無限等于1，此時桶排序的時間復雜度是O(n)
計數(shù)排序
計數(shù)排序可以認為就是一種特殊的桶排序泳秀，特殊在哪兒呢标沪？計數(shù)排序的桶個數(shù)和要排序的數(shù)據(jù)的范圍一致，比如上面數(shù)據(jù)考試成績排序的問題嗜傅，計數(shù)排序的思想就是根據(jù)范圍0~120來建立121個桶金句，將數(shù)據(jù)分布在121個桶。因為每個桶內(nèi)的數(shù)據(jù)是相等的吕嘀，這樣就不用再進行桶內(nèi)排序了违寞，直接按桶順序合起來就可以了。
計數(shù)排序代碼實現(xiàn)
"""
計數(shù)排序
Author: xingrui
"""
# 最大值
def maxNum(nums: list):
maxNumber = nums[0]
for number in nums[1:]:
if maxNumber < number:
maxNumber = number
return maxNumber
# 計數(shù)排序
def countSort(nums: list):
maxNumber = maxNum(nums)
# 初始化數(shù)組大小
countArray = [0] * (maxNumber + 1)
# 將原始數(shù)組的每個元素出現(xiàn)次數(shù)放到countArray中計數(shù)
for number in nums:
countArray[number] += 1
# 累加countArray中的元素偶房，得出在最后結果中的位置關系
for i, item in enumerate(countArray):
if i == 0:
continue
else:
countArray[i] += countArray[i - 1]
result = [0] * len(nums)
for item in nums[::-1]:
countArray[item] -= 1
index = countArray[item]
result[index] = item
return result
if __name__ == "__main__":
nums = [2, 3, 1, 3, 0, 5, 4, 2]
print(countSort(nums))
基數(shù)排序
基數(shù)排序
基數(shù)排序適用的情景比較特殊趁曼，需要數(shù)據(jù)本身是有層次的，比如對單詞進行排序棕洋，對手機號進行排序挡闰，排序的時候會將每個手機號同一個位置的字符拿出來用計數(shù)排序或者桶排序來排序。
代碼實現(xiàn)
"""
基數(shù)排序
Author: xingrui
"""
# 最大值
def maxLength(words: list) -> int:
length = len(words[0])
for word in words[1:]:
if length < len(word):
length = len(word)
return length
# 自動補全
def autoComplete(words: list, length: int):
for i, item in enumerate(words):
if len(item) < length:
words[i] = item + "".join(["0"] * (length - len(item)))
# 基數(shù)排序
def radixSort(words: list):
length = maxLength(words)
autoComplete(words, length)
for index in range(length - 1, -1, -1):
countSort(words, index)
for i, word in enumerate(words):
words[i] = str(word).strip("0")
# 計數(shù)排序
def countSort(words: list, index: int):
# 初始化數(shù)組大小掰盘，ASCII中小寫字母z對應的數(shù)字是122
countArray = [0] * 123
# 將原始數(shù)組的每個元素出現(xiàn)次數(shù)放到countArray中計數(shù)
for word in words:
letter = word[index]
countArray[ord(letter)] += 1
# 累加countArray中的元素摄悯，得出在最后結果中的位置關系
for i, item in enumerate(countArray):
if i == 0:
continue
else:
countArray[i] += countArray[i - 1]
result = [0] * len(words)
for item in words[::-1]:
letter = item[index]
ascii = ord(letter)
countArray[ascii] -= 1
result[countArray[ascii]] = item
if __name__ == "__main__":
words = ["admin", "activity", "birdcage", "heel", "cushion", "fruit",
"background", "bride", "horse", "zebra", "juice", "bridegroom"]
radixSort(words)
print(words)
參考
http://www.reibang.com/p/28ed6963276c
http://www.reibang.com/p/0aff57aa5f8d
http://www.reibang.com/p/be8842b1e5dc
