快捷導(dǎo)航

Python實現(xiàn)的計數(shù)排序算法示例

更新時間：2017年11月29日 12:12:55 作者：愛橙子的OK繃

這篇文章主要介紹了Python實現(xiàn)的計數(shù)排序算法,簡單描述了計數(shù)排序的算法原理并結(jié)合具體實例形式分析了Python計數(shù)排序的相關(guān)實現(xiàn)與使用技巧,需要的朋友可以參考下

本文實例講述了Python實現(xiàn)的計數(shù)排序算法。分享給大家供大家參考，具體如下：

計數(shù)排序是一種非?？旖莸姆€(wěn)定性強的排序方法，時間復(fù)雜度O(n+k),其中n為要排序的數(shù)的個數(shù)，k為要排序的數(shù)的組大值。計數(shù)排序?qū)σ欢康恼麛?shù)排序時候的速度非?？?，一般快于其他排序算法。但計數(shù)排序局限性比較大，只限于對整數(shù)進行排序。計數(shù)排序是消耗空間發(fā)雜度來獲取快捷的排序方法，其空間發(fā)展度為O（K）同理K為要排序的最大值。

計數(shù)排序的基本思想為一組數(shù)在排序之前先統(tǒng)計這組數(shù)中其他數(shù)小于這個數(shù)的個數(shù)，則可以確定這個數(shù)的位置。例如要排序的數(shù)為 7 4 2 1 5 3 1 5；則比7小的有7個數(shù)，所有7應(yīng)該在排序好的數(shù)列的第八位，同理3在第四位，對于重復(fù)的數(shù)字，1在1位和2位（暫且認為第一個1比第二個1?。?和1一樣位于6位和7位。

示例代碼：

#! /usr/bin/env python
#coding=utf-8
#計數(shù)排序
def CountingSort(a, b, k):
  #c=[0]*(k+1) #let c[0...k] be an all 0 array
  #c=[0 for i in range(0,k+1)]
  c=[]
  for i in range(k+1):
    c.append(0)
  for j in range(len(a)):
    c[a[j]] = c[a[j]] + 1
  for i in range(1, k+1):
    c[i] = c[i] + c[i-1]
  for j in range(len(a)-1, -1, -1):
    b[c[a[j]]-1] = a[j]#!!!!!減一是關(guān)鍵
    c[a[j]] = c[a[j]] - 1
  print b
if __name__ == '__main__':
  a=[2, 5, 3, 0, 2, 3, 0, 3]
  #b=[0]*len(a)
  b=[None for i in range(len(a))]
  print "腳本之家測試結(jié)果："
  CountingSort(a, b, max(a))

運行結(jié)果：