This article example describes the base sorting algorithm implemented in Python. Shared for your reference, as follows:
Radix sort belongs to "distribution sort" (distribution sort), also known as "bucket method" (bucket sort) or bin sort, as the name suggests, it is through the key value of part of the information to be sorted elements are allocated to some "bucket", in order to achieve the sorting effect. As the name suggests, it is through the key-value part of the information, the elements to be sorted are allocated to certain "buckets", in order to achieve the role of sorting, the base sorting method is a stable sorting, and its time complexity is O (nlog(r)m), where r is the number of bases taken and m is the number of heaps, in some cases, the efficiency of the base sorting method is higher than that of the other stable sorting methods. sorting methods.
The realization code is as follows:
#-*- coding: UTF-8 -*-
import numpy as np
def RadixSort(a):
i = 0 # Initialize to single digit ordering
n = 1 # Least significant bit set to 1 (contains 0)
max = (a) # Getting the maximum number in a sorted array
while max/(10**n) > 0: # Get the maximum number of digits
n += 1
while i < n:
bucket = {} #Build buckets from dictionaries
for x in xrange(0,10):
(x, []) # Empty every barrel
for x in a: # Sort each bit
radix =(x / (10**i)) % 10 # Getting the base number for each
bucket[radix].append(x) # Add the corresponding array element to the bucket of the corresponding bit base
j = 0
for k in xrange(0, 10):
if len(bucket[k]) != 0: # If the bucket is not empty
for y in bucket[k]: # Put each element in the bucket
a[j] = y # Put it back in the array
j += 1
i += 1
if __name__ == '__main__':
a = (0, 1000, size = 10)
print "Before sorting..."
print "---------------------------------------------------------------"
print a
print "---------------------------------------------------------------"
RadixSort(a)
print "After sorting..."
print "---------------------------------------------------------------"
print a
print "---------------------------------------------------------------"
Run results:
Readers interested in more Python related content can check out this site's topic: thePython Data Structures and Algorithms Tutorial》、《Summary of Python encryption and decryption algorithms and techniques》、《Summary of Python coding manipulation techniques》、《Summary of Python function usage tips》、《Summary of Python string manipulation techniquesand thePython introductory and advanced classic tutorials》
I hope that what I have said in this article will help you in Python programming.