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))

2小時內可以學會Python的基本編程概念和技能。 1.學習變量和數據類型,2.掌握控制流(條件語句和循環),3.理解函數的定義和使用,4.通過簡單示例和代碼片段快速上手Python編程。

Python在web開發、數據科學、機器學習、自動化和腳本編寫等領域有廣泛應用。 1)在web開發中,Django和Flask框架簡化了開發過程。 2)數據科學和機器學習領域,NumPy、Pandas、Scikit-learn和TensorFlow庫提供了強大支持。 3)自動化和腳本編寫方面,Python適用於自動化測試和系統管理等任務。

兩小時內可以學到Python的基礎知識。 1.學習變量和數據類型,2.掌握控制結構如if語句和循環,3.了解函數的定義和使用。這些將幫助你開始編寫簡單的Python程序。

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

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

Python3.6環境下加載Pickle文件報錯:ModuleNotFoundError:Nomodulenamed...

如何解決jieba分詞在景區評論分析中的問題?當我們在進行景區評論分析時,往往會使用jieba分詞工具來處理文�...

如何使用正則表達式匹配到第一個閉合標籤就停止?在處理HTML或其他標記語言時,常常需要使用正則表達式來�...


熱AI工具

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

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

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

AI Hentai Generator
免費產生 AI 無盡。

熱門文章

熱工具

Safe Exam Browser
Safe Exam Browser是一個安全的瀏覽器環境,安全地進行線上考試。該軟體將任何電腦變成一個安全的工作站。它控制對任何實用工具的訪問,並防止學生使用未經授權的資源。

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

Dreamweaver CS6
視覺化網頁開發工具

MinGW - Minimalist GNU for Windows
這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。

PhpStorm Mac 版本
最新(2018.2.1 )專業的PHP整合開發工具