python計數排序和基數排序算法實例

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

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

一、計數排序

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

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

以下是測試代碼：

復制代碼代碼如下:

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

def jishu(data, max):
    """
    基數排序:當輸入的元素是 n 個 0 到 k 之間的整數時(k不能太大,即max不能太大)
    @param data: 需要排序的數組
    @param max: 最大的數
    """
    result = [None for i in xrange(len(data))] # 最后的結果
    c = [0 for i in range(max+1)]
    # 用數組c統計每個值=d的元素個數
    for d in data:
        c[d] = c[d] + 1

    # c[i]表示data中值<=i 的元素個數
    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的數字

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

二、基數排序

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

它是這樣實現的：將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然后，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數列就變成一個有序序列。
基數排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。

以下是一個測試用例：

復制代碼代碼如下:

#-*- coding:utf8 -*-
import random
def jichu(data, length):
    """
    基數排 lsd
    @param data: 需要排列的組合
    @param length: 最大的數據是幾位
    """
    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個數據
print jichu(list, 8)

您可能感興趣的文章: