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 """
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))
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
更新日志
- 《幸福工厂》无限报错解决方法
- 交错战线原始交易所推荐角色一览
- 战锤40K星际战士2战术职业介绍|战术职业技能效果一览
- 战锤40K星际战士2突击职业介绍|突击职业技能效果一览
- [妙音金曲]群星《悲情咖啡屋》(黑胶)2CD[DTS-WAV]
- 阿兰·达瓦卓玛《A-Lan阿兰唯美歌姬》2CD[DTS-WAV]
- 【小提琴】陈立新《思乡曲》2004[FLAC+CUE]
- 《战地》新作明年初大规模测试!EA已内部测试一年
- 《GTAOL》PC版时隔多年更新反作弊!小助手宣布跑路
- EA称AI是其业务核心!能提高开发效率、节约成本
- 卫华.1990-太阳升【BMG】【WAV+CUE】
- 呼吸乐队.1992-THEBREATHING【深飞】【WAV+CUE】
- 李玟.2008-1994-2008豪华典藏精选2CD【SONY】【WAV+CUE】
- 《张学友 再现歌神的光辉岁月 梦想成真 2CD》[WAV/分轨][1.2GB]
- 《海来阿木 高音测试王》[WAV+CUE][500MB]