Python實現(xiàn)的計數排序算法示例
本文實例講述了Python實現(xiàn)的計數排序算法。分享給大家供大家參考，具體如下：
計數排序是一種非?？旖莸姆€(wěn)定性強的排序方法，時間復雜度O(n+k),其中n為要排序的數的個數，k為要排序的數的組大值。計數排序對一定量的整數排序時候的速度非?？?，一般快于其他排序算法。但計數排序局限性比較大，只限于對整數進行排序。計數排序是消耗空間發(fā)雜度來獲取快捷的排序方法，其空間發(fā)展度為O（K）同理K為要排序的最大值。
計數排序的基本思想為一組數在排序之前先統(tǒng)計這組數中其他數小于這個數的個數，則可以確定這個數的位置。例如要排序的數為 7 4 2 1 5 3 1 5；則比7小的有7個數，所有7應該在排序好的數列的第八位，同理3在第四位，對于重復的數字，1在1位和2位（暫且認為第一個1比第二個1?。?，5和1一樣位于6位和7位。
示例代碼：
#! /usr/bin/env python
#coding=utf-8
#計數排序
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]#!!!!!減一是關鍵
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 "腳本之家測試結果："
CountingSort(a, b, max(a))
運行結果：
PS：關于排序算法的詳細說明還可參考本站在線工具：
在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具
http://tools.jb51.net/aideddesign/paixu_ys
更多關于Python相關內容感興趣的讀者可查看本站專題：《Python數據結構與算法教程》、《Python加密解密算法與技巧總結》、《Python編碼操作技巧總結》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經典教程》
希望本文所述對大家Python程序設計有所幫助。
相關文章
這篇文章主要為大家詳細介紹了python實現(xiàn)kMeans算法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-12-12
Menu控件（菜單控件）可以說是 GUI 中“精髓所在”，它以可視化的方式將一系列的命令進行分組，在每一個分組下又可以“隱藏”許多的程序執(zhí)行命令（即功能）。本文將詳細介紹它的使用，需要的可以參考一下2022-01-01
雙向RNN:bidirectional_dynamic_rnn()函數的使用詳解
今天小編就為大家分享一篇雙向RNN:bidirectional_dynamic_rnn()函數的使用詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-01-01
Keras目標檢測mtcnn?facenet搭建人臉識別平臺
這篇文章主要為大家介紹了Keras目標檢測mtcnn?facenet搭建人臉識別平臺，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-05-05
這篇文章主要介紹了詳解python里的命名規(guī)范，命名應當盡量使用全拼寫的單詞，縮寫的情況文章中也給大家提到，需要的朋友參考下吧2018-07-07
python使用socket創(chuàng)建tcp服務器和客戶端
這篇文章主要為大家詳細介紹了python使用socket創(chuàng)建tcp服務器和客戶端，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-04-04
今天我就當回媒婆,給男性程序員來點福利.今天目標爬取征婚網上呈現(xiàn)出來的女生信息保存成excel表格供大家篩選心儀的女生,需要的朋友可以參考下2021-06-06
這篇文章主要介紹了python中的各種運算符，主要包括內容有比較運算符、?賦值運算符、位運算符、邏輯運算符、?成員運算符的相關介紹，需要的小伙伴可以參考一下2022-04-04
這篇文章主要介紹了Python中的路徑問題，幫助大家更好的理解和學習python，感興趣的朋友可以了解下2020-09-09
這篇文章主要介紹了Python 如何在局部變量域中執(zhí)行代碼，幫助大家更好的理解和學習Python，感興趣的朋友可以了解下2020-08-08