快捷導(dǎo)航

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

更新時(shí)間：2014年04月25日 11:50:37 作者：

這篇文章主要介紹了python計(jì)數(shù)排序和基數(shù)排序算法實(shí)例,需要的朋友可以參考下

一、計(jì)數(shù)排序

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

算法的步驟如下：
找出待排序的數(shù)組中最大和最小的元素
統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)
對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開(kāi)始，每一項(xiàng)和前一項(xiàng)相加）
反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1
當(dāng)輸入的元素是 n 個(gè) 0 到 k 之間的整數(shù)時(shí),計(jì)數(shù)排序的時(shí)間復(fù)雜度為O(N+K)，空間復(fù)雜度為O(N+K)。當(dāng)K不是很大時(shí)，這是一個(gè)很有效的線性排序算法。

以下是測(cè)試代碼：

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

#-*- coding:utf8 -*-
import random

def jishu(data, max):
    """
    基數(shù)排序:當(dāng)輸入的元素是 n 個(gè) 0 到 k 之間的整數(shù)時(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)計(jì)每個(gè)值=d的元素個(gè)數(shù)
    for d in data:
        c[d] = c[d] + 1

    # c[i]表示data中值<=i 的元素個(gè)數(shù)
    for i in range(1, max+1):
        c[i] = c[i] + c[i-1]

    # 在將C中的元素倒著打印出來(lái)就是排序好的
    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個(gè)0到100的數(shù)字

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

二、基數(shù)排序

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

它是這樣實(shí)現(xiàn)的：將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開(kāi)始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個(gè)有序序列。
基數(shù)排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開(kāi)始，而MSD則相反，由鍵值的最左邊開(kāi)始。

以下是一個(gè)測(cè)試用例：

復(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個(gè)數(shù)據(jù)
print jichu(list, 8)

您可能感興趣的文章: