一、計數(shù)排序

    計數(shù)排序(Counting sort)是一種穩(wěn)定的排序算法

    算法的步驟如下：

    找出待排序的數(shù)組中最大和最小的元素

    統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項

    對所有的計數(shù)累加（從C中的第一個元素開始，每一項和前一項相加）

    反向填充目標(biāo)數(shù)組：將每個元素i放在新數(shù)組的第C(i)項，每放一個元素就將C(i)減去1

    當(dāng)輸入的元素是 n 個 0 到 k 之間的整數(shù)時,計數(shù)排序的時間復(fù)雜度為O(N+K)，空間復(fù)雜度為O(N+K)，

python計數(shù)排序和基數(shù)排序算法實例

    以下是測試代碼：

    復(fù)制代碼代碼如下:

    #-*- coding:utf8 -*-

    import random

    def jishu(data, max):

    """

    基數(shù)排序:當(dāng)輸入的元素是 n 個 0 到 k 之間的整數(shù)時(k不能太大,即max不能太大)

    @param data: 需要排序的數(shù)組

    @param max: 最大的數(shù)

    """

    result = [None for i in xrange(len(data))] # 最后的結(jié)果

    c = [0 for i in range(max+1)]

    # 用數(shù)組c統(tǒng)計每個值=d的元素個數(shù)

    for d in data:

    c[d] = c[d] + 1

    # c[i]表示data中值<=i 的元素個數(shù)

    for i in range(1, max+1):

    c[i] = c[i] + c[i-1]

    # 在將C中的元素倒著打印出來就是排序好的

    for j in xrange(len(data)-1, -1, -1):

    result[c[data[j]]-1] = data[j]

    c[data[j]] = c[data[j]] – 1

    return result

    if __name__ == '__main__':

    #制造1000個0到100的數(shù)字

    print jishu([random.randint(0, 100) for i in range(1000)], 100)

    二、基數(shù)排序

    基數(shù)排序排序（英語：Radix sort）是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較。

    它是這樣實現(xiàn)的：將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個有序序列。

    基數(shù)排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。

    以下是一個測試用例：

    復(fù)制代碼代碼如下:

    #-*- coding:utf8 -*-

    import random

    def jichu(data, length):

    """

    基數(shù)排 lsd

    @param data: 需要排列的組合

    @param length: 最大的數(shù)據(jù)是幾位

    """

    for l in xrange(length):

    s = [[] for i in xrange(10)]

    for d in data:

    s[d/(10**l) % 10].append(d)

    data = [d for s_list in s for d in s_list]

    return data

    if __name__ == '__main__':

    list = [random.randint(1, 99999999) for i in xrange(99)] # 制造99個數(shù)據(jù)

    print jichu(list, 8)

您可能感興趣的文章:

python實現(xiàn)排序算法

python算法學(xué)習(xí)之計數(shù)排序?qū)嵗?/p>

python算法學(xué)習(xí)之基數(shù)排序?qū)嵗?/p>

python算法學(xué)習(xí)之桶排序算法實例(分塊排序)

python冒泡排序算法的實現(xiàn)代碼

python選擇排序算法的實現(xiàn)代碼

python插入排序算法的實現(xiàn)代碼

python快速排序代碼實例

python實現(xiàn)的各種排序算法代碼

python 實現(xiàn)堆排序算法代碼

python 實現(xiàn)歸并排序算法

python 算法 排序?qū)崿F(xiàn)快速排序

python 快速排序代碼

python3.0 字典key排序

Python學(xué)習(xí)筆記_數(shù)據(jù)排序方法

    QQ空間 搜狐微博 人人網(wǎng) 開心網(wǎng) 百度搜藏更多

    Tags：python 計數(shù)排序 基數(shù)排序 算法

    復(fù)制鏈接收藏本文打印本文關(guān)閉本文返回首頁

    上一篇：python處理圓角圖片、圓形圖片的例子

    下一篇：windows下wxPython開發(fā)環(huán)境安裝與配置方法

相關(guān)文章

2014-05-05Python中使用動態(tài)變量名的方法

2014-01-01linux系統(tǒng)使用python監(jiān)測網(wǎng)絡(luò)接口獲取網(wǎng)絡(luò)的輸入輸出

2009-09-09python encode和decode的妙用

2013-11-11python list語法學(xué)習(xí)（帶例子）

2014-01-01使用scrapy實現(xiàn)爬網(wǎng)站例子和實現(xiàn)網(wǎng)絡(luò)爬蟲(蜘蛛)的步驟

2014-04-04使用Python獲取CPU、內(nèi)存和硬盤等windowns系統(tǒng)信息的2個例子

2014-06-06Python中的yield淺析

2009-11-11python 文件和路徑操作函數(shù)小結(jié)

2014-04-04python中精確輸出JSON浮點數(shù)的方法

2013-11-11linux環(huán)境下安裝pyramid和新建項目的步驟

文章評論

最 近 更 新

python的urllib模塊顯示下載進(jìn)度示例

理解python多線程（python多線程簡明教程

go和python調(diào)用其它程序并得到程序輸出

python使用urllib2模塊獲取gravatar頭像實

常用python數(shù)據(jù)類型轉(zhuǎn)換函數(shù)總結(jié)

Python tempfile模塊學(xué)習(xí)筆記（臨時文件）

python改變?nèi)罩?logging)存放位置的示例

用實例說明python的*args和**kwargs用法

天翼開放平臺免費(fèi)短信驗證碼接口使用實例

Flask SQLAlchemy一對一,一對多的使用方法

熱 點 排 行

Python入門教程 超詳細(xì)1小時學(xué)會

python 中文亂碼問題深入分析

比較詳細(xì)Python正則表達(dá)式操作指

Python字符串的encode與decode研

Python open讀寫文件實現(xiàn)腳本

Python enumerate遍歷數(shù)組示例應(yīng)

Python 深入理解yield

Python+Django在windows下的開發(fā)

python 文件和路徑操作函數(shù)小結(jié)

python 字符串split的用法分享