基數(shù)排序

• 前言
  • 這就是整個(gè)排序算法的最后一篇了，再深入的后來(lái)提出的排序算法基本上是基于這8中基本的排序算法，不做過(guò)多贅述。
• 概述
  • 這是完全不同于之前的排序理念的一種排序方式，它是非基于比較的整形數(shù)據(jù)排序算法。
  • 基本原理是將整數(shù)按照位數(shù)切割為不同的數(shù)字，然后按照位數(shù)比較。
  • 這種排序不一定只適合整數(shù)，有些數(shù)據(jù)格式有內(nèi)含整數(shù)的可能性。
• 算法思路
  • 把待比較的所有整數(shù)統(tǒng)一化為同樣的數(shù)位長(zhǎng)度，數(shù)位不足前面補(bǔ)0，然后從最低位開(kāi)始，依次排序，顯然，按照這個(gè)步驟，待排序到最后一位數(shù)據(jù)一定有序。

• 算法評(píng)價(jià)

  • 復(fù)雜度分析

    排序名稱最好情況最壞情況平均情況

    基數(shù)排序	O(nlog2n)	O(nlog2n)	O(nlog2n)

  • 穩(wěn)定性
    • 算法穩(wěn)定。

# -*- coding:UTF-8 -*- """ 本模塊實(shí)現(xiàn)了一維整形數(shù)的基數(shù)排序 """ def RadixSort(data=[1, 2, 3, 4, 5]):def getMaxBit(data):'''求出最大數(shù)的位數(shù):param data::return:'''maxData = max(data)bitsNum = 0while maxData:bitsNum += 1maxData //= 10return bitsNumdef getDigit(number, n):'''取number第n位數(shù)字:param number::param n::return:'''p = 1while n > 1:n -= 1p *= 10return number // p % 10length = len(data)bucket = [0]*lengthfor d in range(1, getMaxBit(data)+1):count = [0]*10for i in range(length):count[getDigit(data[i], d)] += 1for i in range(1, 10):count[i] += count[i-1]for i in range(0, length)[::-1]:k = getDigit(data[i], d)bucket[count[k] - 1] = data[i]count[k] -= 1for i in range(0, length):data[i] = bucket[i]print(data)return Noneif __name__ == '__main__':testData = [50, 123, 456, 187, 4, 11, 100]RadixSort(testData)

具體可以查看我的github。?

總結(jié)

以上是生活随笔為你收集整理的排序算法-08基数排序（python实现）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。