A common example of distributive sorting for Python data Structures and algorithms

An example of Python data structure and algorithm is presented in this paper. To share for your reference, specific as follows:

Box sort (bucket sort)

Box sorting is to establish m boxes in advance according to the value range of keywords (1~m). Box sorting requires the keyword type to be of finite type, and there may be infinite boxes, which is of little practical value. Generally, it is used in the intermediate process of cardinality sorting.

Bucket sort is practical application cases of sorting variant, its range of data sets, such as [0, 1) were divided into n subinterval of the same size, each 1 is the interval for a bucket, and then record n not assigned to each barrel. Because keyword sequence is uniform distribution in [0, 1), so as not many 1 1 fall into the same bucket.

The following bucket sorting method USES a dictionary, so there is no need to create extra space for integer types

def BuckSort(A):
 bucks = dict()  #  barrel 
 for i in A:
  bucks.setdefault(i,[]) #  Each bucket defaults to an empty list 
  bucks[i].append(i)  #  Add elements to the corresponding bucket 
 A_sort = []
 for i in range(min(A), max(A)+1):
  if i in bucks:     #  Check to see if there is a bucket with a corresponding number 
   A_sort.extend(bucks[i])  #  Merge the data in the bucket 
 return A_sort

Radix sort

#  Radix sort 
#  Input: Array to be sorted s, keysize Keyword number ,  Number of cases , radix base 
def RadixSort(s, keysize=4, radix=10):
 #  Press the beginning of the keyword k Component distribution  k = 4,3,2,1
 def distribute(s,k):
  box = {r:[] for r in range(radix)}  #  Empty boxes for distribution 
  for item in s:   #  In turn, scanning s[] And put it into a box 
   t = item
   t /= 10**(k-1)
   t %= 10    #  Go to keyword control k position 
   box[t].append(item)
  return box
 #  Rearrange the data according to the assigned result 
 def collect(s,box):
  a = 0
  for i in range(radix):
   s[a:a + len(box[i])] = box[i][:] #  Merge the elements in the box, overwriting the original array 
   a += len(box[i])     #  Add offsets 
 #  The core algorithm 
 for k in range(1,keysize+1):
  box = distribute(s,k)   #  Base allocation 
  collect(s,box)     #  Collate according to the assigned results 

The following is from data Structures and Algorithms: Theory and Practice

Radix sort can be extended to sort by multiple keywords, such as by suit, by number of CARDS.
As if 1, let the linear table have that element to be sorted, and each element contains d keywords {k1,k2... ,kd}, then the linear table refers to the keyword order, for any two elements in the linear table r[i] and r[j], 1 < =i < =j < =n, all satisfy the following ordered relations:
{k1i, k2i,... kdi}, < {k1j,k2j,...,kdj}
Among them, k1 is called the most primary key and kd is called the most secondary key
There are two sorting methods: MSD (most significant digit frist) and LSD (least significant first).

MSD: Sort the groups according to k1, and the elements of the same group. If the keyword k1 is equal, then the groups are sorted into subgroups according to k2, and so on, until the lowest bit kd sorts the subgroups, then the groups are linked together.

LSD: As opposed to MSD, sort first by kd, then by kd-1, and so on.

PS: Here is another demo tool on sorting for your reference:

Online animation demonstration of insert/Select/Bubble/merge/Hill/Quicksort algorithm process tools:
http://tools.ofstack.com/aideddesign/paixu_ys

For more information about Python, please refer to Python Data Structure and Algorithm Tutorial, Python Encryption and Decryption Algorithm and Skills Summary, Python Coding skills Summary, Python Function Use Skills Summary, Python String Manipulation Skills Summary and Python Introduction and Advanced Classic Tutorial.

I hope this article has been helpful in Python programming.