Ten classic sorting algorithms – Series of articles

  1. Bubble sort
  2. Selection sort
  3. Insertion sort
  4. Hill sorting
  5. Merge sort
  6. Quick sort
  7. Heap sort
  8. Count sorting
  9. Bucket sort
  10. Radix sort

Radix sort is a kind of non-comparative integer sort algorithm. Its principle is to cut the integers into different numbers according to the number of digits, and then compare them according to each number. Since integers can also represent strings (such as names or dates) and floating-point numbers in a particular format, radix sort is not restricted to integers.

1. Radix sort vs counting sort vs bucket sort

There are two ways to sort radix:

These three sorting algorithms all use the concept of buckets, but there are obvious differences in the use of buckets:

  • Radix sort: buckets are allocated according to each digit of the key value;
  • Counting sort: each bucket stores a single key;
  • Bucket sorting: Each bucket stores a range of values;

2. GIF demonstration of LSD radix sort

3. JavaScript code implementation

//LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]! =null) {
                while((value = counter[j].shift()) ! =null) { arr[pos++] = value; }}}}return arr;
}
Copy the code

4. Python code implementation

def radix(arr) :
    
    digit = 0
    max_digit = 1
    max_value = max(arr)
    Find the largest number of digits in the list
    while 10**max_digit < max_value:
        max_digit = max_digit + 1
    
    while digit < max_digit:
        temp = [[] for i in range(10)]
        for i in arr:
            Find the digit, digit, and hundred of each element
            t = int((i/10**digit)%10)
            temp[t].append(i)
        
        coll = []
        for bucket in temp:
            for i in bucket:
                coll.append(i)
                
        arr = coll
        digit = digit + 1

    return arr
Copy the code

5. Java code implementation

/** ** for negative numbers, see https://code.i-harness.com/zh-CN/q/e98fa9 */
public class RadixSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // Copy the arR without changing the parameters
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }

    /** * gets the highest number */
    private int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if(maxValue < value) { maxValue = value; }}return maxValue;
    }

    protected int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (longtemp = num; temp ! =0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // In the case of negative numbers, double the number of queues, where [0-9] corresponds to negative numbers and [10-19] corresponds to positive numbers (bucket + 10).
            int[][] counter = new int[mod * 2] [0];

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (intvalue : bucket) { arr[pos++] = value; }}}return arr;
    }

    /** * Automatically expand capacity and save data **@param arr
     * @param value
     */
    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        returnarr; }}Copy the code

PHP code implementation

function radixSort($arr.$maxDigit = null)
{
    if ($maxDigit= = =null) {
        $maxDigit = max($arr);
    }
    $counter = [];
    for ($i = 0; $i < $maxDigit; $i{+ +)for ($j = 0; $j < count($arr); $j++) {
            preg_match_all('/\d/', (string) $arr[$j].$matches);
            $numArr = $matches[0];
            $lenTmp = count($numArr);
            $bucket = array_key_exists($lenTmp - $i - 1.$numArr)? intval($numArr[$lenTmp - $i - 1) :0;
            if(! array_key_exists($bucket.$counter)) {
                $counter[$bucket] = [];
            }
            $counter[$bucket=] []$arr[$j];
        }
        $pos = 0;
        for ($j = 0; $j < count($counter); $j{+ +)$value = null;
            if ($counter[$j]! = =null) {
                while (($value = array_shift($counter[$j))! = =null) {
                    $arr[$pos+ +] =$value; }}}}return $arr;
}
Copy the code