python算法學(xué)習(xí)之計(jì)數(shù)排序?qū)嵗?/h1>
更新時(shí)間：2013年12月18日 10:11:22 作者：
本代碼介紹了python算法學(xué)習(xí)中的計(jì)數(shù)排序?qū)嵗?代碼大家參考使用吧
python算法學(xué)習(xí)之計(jì)數(shù)排序?qū)嵗?/P>
復(fù)制代碼 代碼如下:
# -*- coding: utf-8 -*-
def _counting_sort(A, B, k):
"""計(jì)數(shù)排序，偽碼如下：
COUNTING-SORT(A, B, k)
1 for i ← 0 to k // 初始化存儲(chǔ)區(qū)的值
2 do C[i] ← 0
3 for j ← 1 to length[A] // 為各值計(jì)數(shù)
4 do C[A[j]] ← C[A[j]] + 1
5 ▷ C[i]包含等于i的元素個(gè)數(shù)
6 for i ← 1 to k // 求計(jì)數(shù)和，確定<=各值的元素?cái)?shù)
7 do C[i] ← C[i] + C[i-1]
8 ▷ C[i]包含小于或等于i的元素個(gè)數(shù)
9 for j ← length[A] downto 1
10 do B[C[A[j]]] ← A[j] // 將A[j]值放到對(duì)應(yīng)位置
11 C[A[j]] ← C[A[j]] - 1 // 避免元素相同時(shí)覆蓋同一位置
T(n) = θ(n)
Args:
A (Sequence): 原數(shù)組
B (Sequence): 結(jié)果數(shù)組
k (int): 值上限，假定了所有元素介于[0,k]
"""
len_c = k + 1
C = [0] * len_c
for a in A:
C[a] = C[a] + 1
for i in range(1, len_c):
C[i] = C[i] + C[i-1]
for a in A[::-1]:
B[C[a]-1] = a
C[a] = C[a] - 1
def counting_sort(A):
"""假定A數(shù)組所有元素都介于[0,len(A)-1]"""
B = [0] * len(A)
_counting_sort(A, B, len(A) - 1)
return B
if __name__ == '__main__':
import random, timeit
items = range(10000)
random.shuffle(items)
def test_sorted():
print(items)
sorted_items = sorted(items)
print(sorted_items)
def test_counting_sort():
print(items)
sorted_items = counting_sort(items)
print(sorted_items)
test_methods = [test_sorted, test_counting_sort]
for test in test_methods:
name = test.__name__ # test.func_name
t = timeit.Timer(name + '()', 'from __main__ import ' + name)
print(name + ' takes time : %f' % t.timeit(1))
您可能感興趣的文章:- Python算法的時(shí)間復(fù)雜度和空間復(fù)雜度(實(shí)例解析)
- Python算法中的時(shí)間復(fù)雜度問(wèn)題
- python算法題 鏈表反轉(zhuǎn)詳解
- python算法與數(shù)據(jù)結(jié)構(gòu)之單鏈表的實(shí)現(xiàn)代碼
- python算法與數(shù)據(jù)結(jié)構(gòu)之冒泡排序?qū)嵗斀?/a>
- 詳解python算法之冒泡排序
- Python算法之圖的遍歷
- Python算法輸出1-9數(shù)組形成的結(jié)果為100的所有運(yùn)算式
- python算法演練_One Rule 算法(詳解)
- python算法表示概念掃盲教程
- Python算法應(yīng)用實(shí)戰(zhàn)之棧詳解
- Python算法之棧（stack）的實(shí)現(xiàn)
- Python集成學(xué)習(xí)之Blending算法詳解
相關(guān)文章
-
Python項(xiàng)目打包成apk或者其他端的應(yīng)用程序
本文主要介紹了使用Kivy和Buildozer將Python項(xiàng)目打包成Android APK文件的步驟,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧 2024-11-11
-
今天小編就為大家分享一篇python繪制動(dòng)態(tài)曲線教程，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧 2020-02-02
-
python實(shí)現(xiàn)報(bào)表自動(dòng)化詳解
這篇文章主要介紹了python實(shí)現(xiàn)報(bào)表自動(dòng)化詳解，涉及python讀，寫(xiě)excel—xlwt常用功能，xlutils 常用功能，xlwt寫(xiě)Excel時(shí)公式的應(yīng)用等相關(guān)內(nèi)容，具有一定參考價(jià)值，需要的朋友可以了解下。 2017-11-11
-
matplotlib 使用 plt.savefig() 輸出圖片去除旁邊的空白區(qū)域
這篇文章主要介紹了matplotlib 使用 plt.savefig() 輸出圖片去除旁邊的空白區(qū)域，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧 2021-01-01
-
python的數(shù)組切片操作很強(qiáng)大,但有些細(xì)節(jié)老是忘,故寫(xiě)一點(diǎn)東西記錄下來(lái),下面這篇文章主要給大家介紹了關(guān)于Python中數(shù)組切片用法的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),需要的朋友可以參考下 2022-12-12
-
最近寫(xiě)了Python函數(shù)的功能，犯了一些錯(cuò)誤。所以本文主要和大家一起梳理下Python函數(shù)的傳參機(jī)制，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下 2022-07-07
-
機(jī)器學(xué)習(xí)數(shù)據(jù)預(yù)處理之獨(dú)熱One-Hot編碼及其代碼詳解
獨(dú)熱編碼即 One-Hot 編碼，又稱一位有效編碼。其方法是使用 N位 狀態(tài)寄存器來(lái)對(duì) N個(gè)狀態(tài) 進(jìn)行編碼，每個(gè)狀態(tài)都有它獨(dú)立的寄存器位，并且在任意時(shí)候，其中只有一位有效，這篇文章主要介紹了機(jī)器學(xué)習(xí)數(shù)據(jù)預(yù)處理之獨(dú)熱One-Hot編碼及其代碼詳解,需要的朋友可以參考下 2022-07-07
-
Python爬蟲(chóng)突破反爬蟲(chóng)機(jī)制知識(shí)點(diǎn)總結(jié)
在本篇文章里小編給大家整理了一篇關(guān)于Python爬蟲(chóng)突破反爬蟲(chóng)機(jī)制知識(shí)點(diǎn)總結(jié)內(nèi)容，有需要的朋友們可以跟著學(xué)習(xí)下。 2021-11-11
-
當(dāng)我們?cè)谑褂肞yInstaller打包Python程序時(shí),可能會(huì)遇到PyInstaller與pathlib包不兼容的問(wèn)題,這個(gè)錯(cuò)誤的原因是,pathlib這個(gè)包在?Python3.4版本之后已經(jīng)成為了Python標(biāo)準(zhǔn)庫(kù)的一部分,所以不需要再單獨(dú)安裝,所以本文給大家介紹了PyInstaller與pathlib包不兼容的解決方法 2024-12-12
-
python3+PyQt5實(shí)現(xiàn)自定義分?jǐn)?shù)滑塊部件
這篇文章主要為大家詳細(xì)介紹了python3+PyQt5實(shí)現(xiàn)自定義分?jǐn)?shù)滑塊部件，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下 2018-04-04
最新評(píng)論
python算法學(xué)習(xí)之計(jì)數(shù)排序?qū)嵗?/P>
# -*- coding: utf-8 -*-
def _counting_sort(A, B, k):
"""計(jì)數(shù)排序，偽碼如下：
COUNTING-SORT(A, B, k)
1 for i ← 0 to k // 初始化存儲(chǔ)區(qū)的值
2 do C[i] ← 0
3 for j ← 1 to length[A] // 為各值計(jì)數(shù)
4 do C[A[j]] ← C[A[j]] + 1
5 ▷ C[i]包含等于i的元素個(gè)數(shù)
6 for i ← 1 to k // 求計(jì)數(shù)和，確定<=各值的元素?cái)?shù)
7 do C[i] ← C[i] + C[i-1]
8 ▷ C[i]包含小于或等于i的元素個(gè)數(shù)
9 for j ← length[A] downto 1
10 do B[C[A[j]]] ← A[j] // 將A[j]值放到對(duì)應(yīng)位置
11 C[A[j]] ← C[A[j]] - 1 // 避免元素相同時(shí)覆蓋同一位置
T(n) = θ(n)
Args:
A (Sequence): 原數(shù)組
B (Sequence): 結(jié)果數(shù)組
k (int): 值上限，假定了所有元素介于[0,k]
"""
len_c = k + 1
C = [0] * len_c
for a in A:
C[a] = C[a] + 1
for i in range(1, len_c):
C[i] = C[i] + C[i-1]
for a in A[::-1]:
B[C[a]-1] = a
C[a] = C[a] - 1
def counting_sort(A):
"""假定A數(shù)組所有元素都介于[0,len(A)-1]"""
B = [0] * len(A)
_counting_sort(A, B, len(A) - 1)
return B
if __name__ == '__main__':
import random, timeit
items = range(10000)
random.shuffle(items)
def test_sorted():
print(items)
sorted_items = sorted(items)
print(sorted_items)
def test_counting_sort():
print(items)
sorted_items = counting_sort(items)
print(sorted_items)
test_methods = [test_sorted, test_counting_sort]
for test in test_methods:
name = test.__name__ # test.func_name
t = timeit.Timer(name + '()', 'from __main__ import ' + name)
print(name + ' takes time : %f' % t.timeit(1))
- Python算法的時(shí)間復(fù)雜度和空間復(fù)雜度(實(shí)例解析)
- Python算法中的時(shí)間復(fù)雜度問(wèn)題
- python算法題 鏈表反轉(zhuǎn)詳解
- python算法與數(shù)據(jù)結(jié)構(gòu)之單鏈表的實(shí)現(xiàn)代碼
- python算法與數(shù)據(jù)結(jié)構(gòu)之冒泡排序?qū)嵗斀?/a>
- 詳解python算法之冒泡排序
- Python算法之圖的遍歷
- Python算法輸出1-9數(shù)組形成的結(jié)果為100的所有運(yùn)算式
- python算法演練_One Rule 算法(詳解)
- python算法表示概念掃盲教程
- Python算法應(yīng)用實(shí)戰(zhàn)之棧詳解
- Python算法之棧（stack）的實(shí)現(xiàn)
- Python集成學(xué)習(xí)之Blending算法詳解
相關(guān)文章
-
Python項(xiàng)目打包成apk或者其他端的應(yīng)用程序
本文主要介紹了使用Kivy和Buildozer將Python項(xiàng)目打包成Android APK文件的步驟,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2024-11-11 - 今天小編就為大家分享一篇python繪制動(dòng)態(tài)曲線教程，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-02-02
-
python實(shí)現(xiàn)報(bào)表自動(dòng)化詳解
這篇文章主要介紹了python實(shí)現(xiàn)報(bào)表自動(dòng)化詳解，涉及python讀，寫(xiě)excel—xlwt常用功能，xlutils 常用功能，xlwt寫(xiě)Excel時(shí)公式的應(yīng)用等相關(guān)內(nèi)容，具有一定參考價(jià)值，需要的朋友可以了解下。2017-11-11 -
matplotlib 使用 plt.savefig() 輸出圖片去除旁邊的空白區(qū)域
這篇文章主要介紹了matplotlib 使用 plt.savefig() 輸出圖片去除旁邊的空白區(qū)域，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01 - python的數(shù)組切片操作很強(qiáng)大,但有些細(xì)節(jié)老是忘,故寫(xiě)一點(diǎn)東西記錄下來(lái),下面這篇文章主要給大家介紹了關(guān)于Python中數(shù)組切片用法的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-12-12
- 最近寫(xiě)了Python函數(shù)的功能，犯了一些錯(cuò)誤。所以本文主要和大家一起梳理下Python函數(shù)的傳參機(jī)制，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2022-07-07
-
機(jī)器學(xué)習(xí)數(shù)據(jù)預(yù)處理之獨(dú)熱One-Hot編碼及其代碼詳解
獨(dú)熱編碼即 One-Hot 編碼，又稱一位有效編碼。其方法是使用 N位 狀態(tài)寄存器來(lái)對(duì) N個(gè)狀態(tài) 進(jìn)行編碼，每個(gè)狀態(tài)都有它獨(dú)立的寄存器位，并且在任意時(shí)候，其中只有一位有效，這篇文章主要介紹了機(jī)器學(xué)習(xí)數(shù)據(jù)預(yù)處理之獨(dú)熱One-Hot編碼及其代碼詳解,需要的朋友可以參考下2022-07-07 -
Python爬蟲(chóng)突破反爬蟲(chóng)機(jī)制知識(shí)點(diǎn)總結(jié)
在本篇文章里小編給大家整理了一篇關(guān)于Python爬蟲(chóng)突破反爬蟲(chóng)機(jī)制知識(shí)點(diǎn)總結(jié)內(nèi)容，有需要的朋友們可以跟著學(xué)習(xí)下。2021-11-11 - 當(dāng)我們?cè)谑褂肞yInstaller打包Python程序時(shí),可能會(huì)遇到PyInstaller與pathlib包不兼容的問(wèn)題,這個(gè)錯(cuò)誤的原因是,pathlib這個(gè)包在?Python3.4版本之后已經(jīng)成為了Python標(biāo)準(zhǔn)庫(kù)的一部分,所以不需要再單獨(dú)安裝,所以本文給大家介紹了PyInstaller與pathlib包不兼容的解決方法2024-12-12
-
python3+PyQt5實(shí)現(xiàn)自定義分?jǐn)?shù)滑塊部件
這篇文章主要為大家詳細(xì)介紹了python3+PyQt5實(shí)現(xiàn)自定義分?jǐn)?shù)滑塊部件，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-04-04