桶排序和計數(shù)排序

桶排序

在說計數(shù)排序之前需要先提一下桶排序，因為計數(shù)排序?qū)嶋H上可以被認為是一種特殊的桶排序。
桶排序，顧名思義，需要準備很多桶，比如在一次數(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è)數(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中的元素，得出在最后結(jié)果中的位置關(guān)系
    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中的元素，得出在最后結(jié)果中的位置關(guān)系
    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.itdecent.cn/p/28ed6963276c
http://www.itdecent.cn/p/0aff57aa5f8d
http://www.itdecent.cn/p/be8842b1e5dc