Examples of python counting sort and radix sort algorithms

Count sort

Counting sort is a stable sorting algorithm

The steps of the algorithm are as follows:
Find the largest and smallest elements in the array to be sorted
Count the number of occurrences of each element with value I in the array, and store the ith item in the array C
Add up all the counts (starting with the first element in C, each term and the previous term)
Backfill the target array: place each element I in the C(I) of the new array, subtracting C(I) from 1 for each element
When the input elements are n integers between 0 and k, the time complexity of counting sort is O(n + k) and the space complexity is O(n + k). This is a very efficient linear sorting algorithm when K is not very large.

Here is the test code:

#-*- coding:utf8 -*-
import random

def jishu(data, max):
    """
     Radix sort : When the input element is  n  a  0  to  k  Between the integers (k Not too big , namely max Not too big )
    @param data:  The array that needs to be sorted 
    @param max:  The biggest number of 
    """
    result = [None for i in xrange(len(data))]  #  The end result 
    c = [0 for i in range(max+1)]
    #  With an array c Count each value =d The number of elements 
    for d in data:
        c[d] = c[d] + 1
    # c[i] said data The median <=i  The number of elements 
    for i in range(1, max+1):
        c[i] = c[i] + c[i-1]
    #  In the C Is printed upside down and sorted 
    for j in xrange(len(data)-1, -1, -1):
        result[c[data[j]]-1] = data[j]
        c[data[j]] = c[data[j]]  �  1
    return result
 
if __name__ == '__main__':
    # manufacturing 1000 a 0 to 100 The number of 
    print jishu([random.randint(0, 100) for i in range(1000)], 100)

2. Radix sort

Radix sort (English: Radix sort) is a noncomparative integer sorting algorithm that cuts integers into digits and compares them separately.

It works like this: all values to be compared (positive integers) are unified into the same digit length, and the shorter digits are zeroed. Then, starting with the lowest order, you sort them one at a time. In this way, the sequence becomes an ordered sequence from the lowest order to the highest order.
Radix sort can be done in a way that is LSD (Least significant digital) or MSD (Most significant digital), with LSD starting at the rightmost of the key and MSD starting at the leftmost of the key.

Here is a test case:

#-*- coding:utf8 -*-
import random
def jichu(data, length):
    """
     The base line  lsd 
    @param data:  You need a combination of permutations 
    @param length:  The largest number is the number of bits 
    """
    for l in xrange(length):
        s = [[] for i in xrange(10)]  
        for d in data:
            s[d/(10**l) % 10].append(d)
        data = [d for s_list in s for d in s_list]
    return data
 
if __name__ == '__main__':
    list = [random.randint(1, 99999999) for i in xrange(99)]  #  manufacturing 99 A data 
    print jichu(list, 8)