python算法学习之计数排序实例
python算法学习之计数排序实例
代码如下:
# -*- coding: utf-8 -*-
def _counting_sort(A, B, k):
"""计数排序,伪码如下:
COUNTING-SORT(A, B, k)
1 for i ← 0 to k // 初始化存储区的值
2 do C[i] ← 0
3 for j ← 1 to length[A] // 为各值计数
4 do C[A[j]] ← C[A[j]] + 1
5 ▷ C[i]包含等于i的元素个数
6 for i ← 1 to k // 求计数和,确定 7 do C[i] ← C[i] + C[i-1]
8 ▷ C[i]包含小于或等于i的元素个数
9 for j ← length[A] downto 1
10 do B[C[A[j]]] ← A[j] // 将A[j]值放到对应位置
11 C[A[j]] ← C[A[j]] - 1 // 避免元素相同时覆盖同一位置
T(n) = θ(n)
Args:
A (Sequence): 原数组
B (Sequence): 结果数组
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数组所有元素都介于[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))

熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

記事本++7.3.1
好用且免費的程式碼編輯器

SublimeText3漢化版
中文版,非常好用

禪工作室 13.0.1
強大的PHP整合開發環境

Dreamweaver CS6
視覺化網頁開發工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)

Linux終端中查看Python版本時遇到權限問題的解決方法當你在Linux終端中嘗試查看Python的版本時,輸入python...

使用FiddlerEverywhere進行中間人讀取時如何避免被檢測到當你使用FiddlerEverywhere...

在使用Python的pandas庫時,如何在兩個結構不同的DataFrame之間進行整列複製是一個常見的問題。假設我們有兩個Dat...

如何在10小時內教計算機小白編程基礎?如果你只有10個小時來教計算機小白一些編程知識,你會選擇教些什麼�...

Uvicorn是如何持續監聽HTTP請求的? Uvicorn是一個基於ASGI的輕量級Web服務器,其核心功能之一便是監聽HTTP請求並進�...

攻克Investing.com的反爬蟲策略許多人嘗試爬取Investing.com(https://cn.investing.com/news/latest-news)的新聞數據時,常常�...
