def counting_sort(a, k):
""" k為a數(shù)組中的最大值 """
# 構(gòu)造臨時緩存數(shù)組c
c = [0 for _ in range(k + 1)]
# 初始化結(jié)果數(shù)組b
b = [0 for _ in range(len(a))]
# c[a[j]] 表示的是全庸，a[j]元素的數(shù)值在c中有對應(yīng)的下標數(shù)值纺蛆，則加1
# c數(shù)組中的元素代表對應(yīng)下標數(shù)字在a數(shù)組中存在的個數(shù)
# c = [0, 0, 0] a = [2, 1, 1]
# >>> c = [0, 2, 1]
for n in range(0, len(a)):
c[a[n]] = c[a[n]] + 1
# 計算有多少個元素小于等于c的下標元素數(shù)值
for _ in range(1, k + 1):
c[_] = c[_] + c[_ - 1]
# a = [2, 5, 3, 0, 2, 3, 0, 3]
# c = [2, 2, 4, 7, 7, 8]
# b[c[a[8]] - 1] = b[c[3] - 1] = b[7 - 1] = a[8] = 3
# b = [0, 0, 0, 0, 0, 0, 3, 0]
# b[c[a[7]] - 1] = b[c[0] - 1] = b[2 - 1] = a[7] = 0
# b = [0, 0, 0, 0, 0, 0, 3, 0]
# b[c[a[6]] - 1] = b[c[3] - 1] = b[6 - 1] = a[6] = 3
# b = [0, 0, 0, 0, 0, 3, 3, 0]
# ...
for m in range(len(a) - 1, -1, -1):
b[c[a[m]] - 1] = a[m]
c[a[m]] = c[a[m]] - 1
return b
if __name__ == '__main__':
a = [2, 5, 3, 0, 2, 3, 0, 3]
print(counting_sort(a, 5))
# [0, 0, 2, 2, 3, 3, 3, 5]
計數(shù)排序
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門蛾号，熙熙樓的掌柜王于貴愁眉苦臉地迎上來屋讶，“玉大人，你說我怎么就攤上這事须教∶笊” “怎么了斩芭？”我有些...
- 文/不壞的土叔 我叫張陵，是天一觀的道長乐疆。 經(jīng)常有香客問我划乖，道長，這世上最難降的妖魔是什么挤土？ 我笑而不...
- 正文 為了忘掉前任琴庵，我火速辦了婚禮，結(jié)果婚禮上仰美，老公的妹妹穿的比我還像新娘迷殿。我一直安慰自己，他們只是感情好咖杂，可當我...
- 文/花漫 我一把揭開白布庆寺。 她就那樣靜靜地躺著，像睡著了一般诉字。 火紅的嫁衣襯著肌膚如雪懦尝。 梳的紋絲不亂的頭發(fā)上，一...
- 文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼漠趁！你這毒婦竟也來了扁凛？” 一聲冷哼從身側(cè)響起闯传，我...
- 正文 年R本政府宣布，位于F島的核電站轴猎，受9級特大地震影響嵌莉，放射性物質(zhì)發(fā)生泄漏税稼。R本人自食惡果不足惜垮斯，卻給世界環(huán)境...
- 文/蒙蒙 一郎仆、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧兜蠕，春花似錦扰肌、人聲如沸。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至晶府，卻和暖如春桂躏，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背川陆。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- 一.計數(shù)排序 算法原理 1.找出待排序的數(shù)組中最大和最小的元素2.統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組c...
- 上次把時間復(fù)雜度趨近于O（nlogn）的算法寫完了控轿，這次先接著把時間復(fù)雜度O（n）的兩個算法寫完冤竹。它們分別是計數(shù)排...
- 閱讀經(jīng)典——《算法導(dǎo)論》07 到目前為止贴见，我們已經(jīng)介紹了插入排序烘苹、歸并排序、堆排序片部、快速排序這四種排序算法镣衡，他們的...
- 數(shù)據(jù)結(jié)構(gòu)與算法——計數(shù)排序辖所、桶排序惰说、基數(shù)排序 計數(shù)排序 計數(shù)排序有如下四個步驟。 首先會對每個輸入進行頻率統(tǒng)計缘回，得...
- 目錄 1酥宴、前言2啦吧、計數(shù)排序3、基數(shù)排序4拙寡、使用場景 1授滓、前言 常見的排序算法有很多，例如歸并排序肆糕、堆排序般堆、快速排序...
