forked from sphinxyun/algorithm-in-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathradixSort.py
More file actions
52 lines (47 loc) · 1.4 KB
/
radixSort.py
File metadata and controls
52 lines (47 loc) · 1.4 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
''' mbinary
#########################################################################
# File : radixSort.py
# Author: mbinary
# Mail: [email protected]
# Blog: https://mbinary.xyz
# Github: https://github.com/mbinary
# Created Time: 2018-07-06 15:52
# Description:
#########################################################################
'''
def radixSort(lst,radix=10):
ls = [[] for i in range(radix)]
mx = max(lst)
weight = 1
while mx >= weight:
for i in lst:
ls[(i // weight)%radix].append(i)
weight *= radix
lst = sum(ls,[])
ls = [[] for i in range(radix)]
return lst
def countSort(lst,mn,mx):
mark = [0]*(mx-mn+1)
for i in lst:
mark[i-mn]+=1
ret =[]
for n,i in enumerate(mark):
ret +=[n+mn]*i
return ret
from quickSort import quickSort
from time import time
from random import randint
def timer(funcs,span,num=1000000):
lst = [randint(0,span) for i in range(num)]
print('range({}), {} items'.format(span,num))
for func in funcs:
data = lst.copy()
t = time()
func(data)
t = time()-t
print('{}: {}s'.format(func.__name__,t))
if __name__ == '__main__':
timer([quickSort,radixSort,sorted],1000000000000,1000)
timer([quickSort,radixSort,sorted],10000,100000)
lst = [randint(0,100) for i in range(1000)]
print(countSort(lst,0,100)==sorted(lst))