时间:2021-05-22
基数排序法又称桶子法(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些"桶"中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的比较性排序法。
复制代码 代码如下:
# -*- coding: utf-8 -*-
def _counting_sort(A, i):
"""计数排序,以i位进行排序,以适用于基数排序。
Args:
A (Sequence): 排序数组
i (int): 位数,从0开始而不是1
"""
C = [0] * 10 # 任意位值范围为[0,9]
A = [(a / (10 ** i) % 10, a) for a in A] # 元素i位值及其自身的元组的数组
for k, a in A:
C[k] = C[k] + 1
for i in xrange(1, 10):
C[i] = C[i] + C[i-1]
B = [0] * len(A) # 结果数组
for k, a in A[::-1]:
B[C[k]-1] = a
C[k] = C[k] - 1
return B
def radix_sort(A, d):
"""基数排序,从最低位进行排序直到最高位:
RADIX-SORT(A, d)
1 for i ← 1 to d
2 do use a stable sort to sort array A on digit i
Args:
A (Sequence): 排序数组
d (int): 最大数位数
"""
for i in xrange(d): # 遍历位数,从低到高
A = _counting_sort(A, i)
return A
def rsort(A, d):
"""基数排序(桶排序版本)"""
for i in xrange(d): # 遍历位数,从低到高
S = [[] for _ in xrange(10)] # 存放[0,9]位数值所对应元素([0-9]10个桶)
for a in A: # 遍历元素
S[a / (10 ** i) % 10].append(a) # 存放对应位数值的元素(元素当前位值在哪个桶就放进去)
A = [a for b in S for a in b] # 以当前位数值排序好的A(依次从各桶里把元素拿出来)
return A
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_radix_sort():
print(items)
sorted_items = radix_sort(items, 4) # [0,9999],4位数
print(sorted_items)
test_methods = [test_sorted, test_radix_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))
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了Python实现的基数排序算法。分享给大家供大家参考,具体如下:基数排序(radixsort)属于“分配式排序”(distributionsort
本文实例讲述了PHP排序算法之基数排序(RadixSort)。分享给大家供大家参考,具体如下:基数排序在《大话数据结构》中并未讲到,但是为了凑齐八大排序算法,我
本文实例讲述了JS使用队列对数组排列,基数排序算法。分享给大家供大家参考,具体如下:/**使用队列对数组排列,基数排序*对于0~99的数字,基数排序将数组集扫描
本文实例讲述了python简单实现基数排序算法。分享给大家供大家参考。具体实现方法如下:fromrandomimportrandintdefmain():A=[
C++基数排序 大家好,今天带来的是自己实现的用C++完成基数排序.在数据结构,算法分析和程序设计的学习过程中,我们经常也无法避免的要学到排序的算法.排序算法是