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 // 初始化存儲區(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]值放到對應(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ù)雜度問題
- 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實(shí)現(xiàn)網(wǎng)絡(luò)通信的HTTP請求Socket編程Web爬蟲方法探索
隨著互聯(lián)網(wǎng)的不斷發(fā)展,Python作為一門多用途的編程語言,提供了強(qiáng)大的工具和庫來進(jìn)行網(wǎng)絡(luò)連接和通信,本文將深入探討Python中連接網(wǎng)絡(luò)的方法,包括HTTP請求、Socket編程、Web爬蟲和REST?API的使用 2024-01-01
-
這篇文章主要介紹了python函數(shù)局部變量用法,較為詳細(xì)的分析了Python局部變量的原理與使用技巧,并對比分析了局部變量與global全局變量的用法區(qū)別,具有一定參考借鑒價(jià)值,需要的朋友可以參考下 2015-08-08
-
這篇文章主要介紹了selenium跳過webdriver檢測并模擬登錄淘寶，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧 2019-06-06
-
這篇文章主要介紹了Django中使用第三方登錄的示例代碼，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧 2018-08-08
-
pycharm調(diào)試時(shí)顯示圖片問題的解決
這篇文章主要介紹了pycharm調(diào)試時(shí)顯示圖片問題的解決方案，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧 2021-04-04
-
淺談Python數(shù)據(jù)類型判斷及列表腳本操作
下面小編就為大家?guī)硪黄獪\談Python數(shù)據(jù)類型判斷及列表腳本操作。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧 2016-11-11
-
python獲取外網(wǎng)IP并發(fā)郵件的實(shí)現(xiàn)方法
下面小編就為大家?guī)硪黄猵ython獲取外網(wǎng)IP并發(fā)郵件的實(shí)現(xiàn)方法。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧 2017-10-10
-
這篇文章主要介紹了Windows下Sqlmap環(huán)境安裝,本文通過圖文并茂的形式給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下 2020-08-08
-
YOLOv5改進(jìn)之添加SE注意力機(jī)制的詳細(xì)過程
作為當(dāng)前先進(jìn)的深度學(xué)習(xí)目標(biāo)檢測算法YOLOv5,已經(jīng)集合了大量的trick,但是還是有提高和改進(jìn)的空間,針對具體應(yīng)用場景下的檢測難點(diǎn),可以不同的改進(jìn)方法,下面這篇文章主要給大家介紹了關(guān)于YOLOv5改進(jìn)之添加SE注意力機(jī)制的相關(guān)資料,需要的朋友可以參考下 2022-08-08
-
Pandas數(shù)據(jù)清洗和預(yù)處理的實(shí)現(xiàn)示例
本文主要介紹了Pandas數(shù)據(jù)清洗和預(yù)處理的實(shí)現(xiàn)示例,包括處理缺失值、異常值,進(jìn)行數(shù)據(jù)轉(zhuǎn)換和規(guī)范化,以及處理重復(fù)數(shù)據(jù)等操作,感興趣的可以了解一下 2024-01-01
最新評論
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 // 初始化存儲區(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]值放到對應(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ù)雜度問題
- 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實(shí)現(xiàn)網(wǎng)絡(luò)通信的HTTP請求Socket編程Web爬蟲方法探索
隨著互聯(lián)網(wǎng)的不斷發(fā)展,Python作為一門多用途的編程語言,提供了強(qiáng)大的工具和庫來進(jìn)行網(wǎng)絡(luò)連接和通信,本文將深入探討Python中連接網(wǎng)絡(luò)的方法,包括HTTP請求、Socket編程、Web爬蟲和REST?API的使用2024-01-01 - 這篇文章主要介紹了python函數(shù)局部變量用法,較為詳細(xì)的分析了Python局部變量的原理與使用技巧,并對比分析了局部變量與global全局變量的用法區(qū)別,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-08-08
- 這篇文章主要介紹了selenium跳過webdriver檢測并模擬登錄淘寶，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-06-06
- 這篇文章主要介紹了Django中使用第三方登錄的示例代碼，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-08-08
-
pycharm調(diào)試時(shí)顯示圖片問題的解決
這篇文章主要介紹了pycharm調(diào)試時(shí)顯示圖片問題的解決方案，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-04-04 -
淺談Python數(shù)據(jù)類型判斷及列表腳本操作
下面小編就為大家?guī)硪黄獪\談Python數(shù)據(jù)類型判斷及列表腳本操作。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-11-11 -
python獲取外網(wǎng)IP并發(fā)郵件的實(shí)現(xiàn)方法
下面小編就為大家?guī)硪黄猵ython獲取外網(wǎng)IP并發(fā)郵件的實(shí)現(xiàn)方法。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-10-10 - 這篇文章主要介紹了Windows下Sqlmap環(huán)境安裝,本文通過圖文并茂的形式給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-08-08
-
YOLOv5改進(jìn)之添加SE注意力機(jī)制的詳細(xì)過程
作為當(dāng)前先進(jìn)的深度學(xué)習(xí)目標(biāo)檢測算法YOLOv5,已經(jīng)集合了大量的trick,但是還是有提高和改進(jìn)的空間,針對具體應(yīng)用場景下的檢測難點(diǎn),可以不同的改進(jìn)方法,下面這篇文章主要給大家介紹了關(guān)于YOLOv5改進(jìn)之添加SE注意力機(jī)制的相關(guān)資料,需要的朋友可以參考下2022-08-08 -
Pandas數(shù)據(jù)清洗和預(yù)處理的實(shí)現(xiàn)示例
本文主要介紹了Pandas數(shù)據(jù)清洗和預(yù)處理的實(shí)現(xiàn)示例,包括處理缺失值、異常值,進(jìn)行數(shù)據(jù)轉(zhuǎn)換和規(guī)范化,以及處理重復(fù)數(shù)據(jù)等操作,感興趣的可以了解一下2024-01-01