radix sort
ひまつぶし
def maxof(xs, fn): ma = fn(xs[0]) for x in xs: tmp = fn(x) if ma < tmp: ma = tmp return tmp def radix_sort(xs, M): bs = [[] for i in range(M)] N = maxof(xs, len) checks = [0 for _ in range(M)] for x in xs: bs[int(x[-1])].append(x) for i in range(2, N+1): for k in range(M): checks[k] = 0 for j, b in enumerate(bs): for _ in range(checks[j], len(b)): x = b.pop(0) k = int(x[-i]) bs[k].append(x) checks[k] += 1 return bs if __name__ == "__main__": import random xs = [str(random.randint(100, 990)) for i in range(200)] print [x for xs in radix_sort(xs, 10) for x in xs] """ ['101', '112', '113', '118', '119', '124', '128', '133', '136', '137', '140', '147', '152', '154', '159', '164', '167', '169', '178', '179', '186', '191', '193', '193', '196', '220', '223', '224', '233', '234', '244', '246', '247', '247', '256', '264', '266', '273', '280', '288', '288', '290', '297', '300', '301', '302', '308', '313', '323', '340', '346', '348', '350', '350', '355', '367', '368', '375', '376', '386', '387', '396', '400', '405', '407', '414', '416', '420', '426', '431', '436', '439', '441', '445', '445', '445', '446', '453', '455', '459', '461', '473', '498', '501', '515', '517', '522', '529', '531', '540', '541', '542', '544', '545', '546', '563', '566', '573', '573', '574', '576', '577', '588', '588', '591', '595', '598', '599', '605', '606', '612', '616', '624', '625', '626', '638', '640', '644', '660', '663', '665', '668', '673', '676', '677', '680', '683', '688', '689', '690', '693', '694', '696', '697', '699', '699', '704', '705', '710', '719', '719', '724', '733', '735', '742', '742', '753', '781', '782', '785', '786', '787', '792', '796', '802', '806', '807', '808', '813', '814', '817', '822', '824', '829', '835', '836', '836', '840', '840', '843', '845', '852', '859', '859', '863', '891', '891', '893', '893', '895', '895', '897', '902', '903', '910', '912', '914', '916', '916', '925', '926', '939', '945', '956', '956', '962', '963', '968', '969', '986'] """