Classic algorithm: a small example of radix sort

1. An overview of the

Radix sort (Radix sort) is a non-comparative integer sort algorithm. Its principle is to cut integers into different Numbers by bits, and then compare them by each bit. Because 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. The invention of radix sort can be traced back to the 1887 work of Herman holley on the punched card tabulating machine (Tabulation Machine).

Principle: the value to be compared (positive integer) is uniformly 1 to the same digit length, and the shorter digit is filled with zero in front. Then, starting with the lowest bit, sort them one at a time. In this way, from the lowest order order 1 to the highest order order is completed, the sequence becomes an ordered sequence. The time complexity of radix sort is O(k · n), where n is the number of sorted elements and k is the number of digits.

Understand: similar to [classic algorithm] the 8th time: bucket sort, here always need 10 buckets, use for many times, first with the value of the units digit to fill the bucket, that is, the unit digit is 1 into the 1 bucket, 9 into the 9 bucket, and then with the bucket sort of 10 digits, and so on.

If there is an array [62,14,59,88,16] to be sorted, simply point 5 Numbers, allocate 10 buckets, the bucket number is 0-9, take the single-digit number as the bucket number, and put it into the bucket one after another, so as to make the bottom like this

| 0 | 0 | 62 | 0 | 14 | 0 | 16 | 0 | 88 | 59 |

|, 0, |, 1, |, 2, |, 3, |, 4, |, 5, |, 6, |, 7, |, 8, |, 9, |0 barrels number

[62,14,16,88,59]

Into the bucket again, but this time to the number of 10 digits, into the corresponding bucket, into the following: because the front did the order of the units digit, so when the 10 digits are equal, the units digit is from small to large order into the bucket, that is to say, into the bucket or in order

| 0 | 14,16 | 0 | 0 | 0 | 59 | 62 | 0 | 88 | 0 |

|, 0, |, 1, |, 2, |, 3, |, 4, |, 5, |, 6, |, 7, |, 8, |, 9, |0 barrels number

Because there are no Numbers larger than 100, there are no hundreds, so when you get to the end of the sorting, you just take out the order

Final output :[14,16,59,62,88]

Example 2.

// Radix sort  C# Code
        public static void RadixSort(int[] nums, int digit)
        {
            for (int k = 1; k <= digit; k++)
            {
                int[] tmpArray = new int[nums.Length];
                int[] tmpCountingSortArray = new int[10];
                int i;
                for (i = 0; i < nums.Length; i++)
                {
                    int tmpSplitDigit = nums[i] / (int)Math.Pow(10, k - 1) - (nums[i] / (int)Math.Pow(10, k)) * 10;
                    tmpCountingSortArray[tmpSplitDigit]++;
                }
                for (i = 1; i < tmpCountingSortArray.Length; i++)
                {
                    tmpCountingSortArray[i] += tmpCountingSortArray[i - 1];
                }
                for (i = nums.Length - 1; i >= 0; i--)
                {
                    int tmpSplitDigit = nums[i] / (int)Math.Pow(10, k - 1) - (nums[i] / (int)Math.Pow(10, k)) * 10;
                    tmpArray[tmpCountingSortArray[tmpSplitDigit] - 1] = nums[i];
                    tmpCountingSortArray[tmpSplitDigit]--;
                }
                for (i = 0; i < nums.Length; i++)
                {
                    nums[i] = tmpArray[i];
                }
            }
        }
            //int[] list = new[] { 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 };
            //Sorter.RadixSort(list, 2);