JIYIK CN >

Radix Sort : It is a non-comparative integer sorting algorithm.

The basic principle of radix sorting is to group integers according to the number of digits in the integer. In the grouping process, the missing digits are filled with 0.

According to the different order of grouping the digits, radix sorting can be divided into LSD radix sorting and MSD radix sorting.

LSD radix sorting is to sort by grouping from low to high. For example: 1,2,3,4,5,6,7,8,9,10 is 10,1,2,3,4,5,6,7,8,9 after the first grouping.

MSD cardinality sorting is grouping and sorting in order from high to low. For example: 1,2,3,4,5,6,7,8,9,10 After the first grouping, it becomes 1,10,2,3,4,5,6,7,8,9.

The above two methods not only have different order of grouping digits, but also different implementation principles. Here we only introduce LSD radix sorting.

First, let's look at how LSD radix sorting is performed.

Each bit of each integer in the sequence can be regarded as a bucket, and the number on that bit can be regarded as the key value of this bucket. How should this sentence be understood? Let's look at such a sequence

170, 45, 75, 90, 802, 2, 24, 66

This is an integer sequence. We know that the value of each digit of each integer must be between 0 and 9. Therefore, in order to sort this sequence using LSD, there must be 10 buckets. The indexes of these 10 buckets are 0 to 9. For LSD radix sorting, each grouping process is to put the corresponding integer into the corresponding bucket.

For example, for each integer, we need to group them according to the number in the ones digit. So let's look at 170, whose ones digit is 0, so 170 should be put into bucket 0. Then 45 should be put into bucket 5.

So after the first grouping of the above sequence, the buckets where the integers are located are as follows

0: 17 0 , 09 0
1: empty
2: 80 2 , 00 2
3: empty
4: 02 4
5: 04 5 , 07 5
6: 06 6
7–9: empty

Then collect these numbers one by one, and the sequence after the first grouping and recombining is

170, 90, 802, 2, 24, 45, 75, 66

The next step is to group the numbers in the tens place into buckets. The bucketing is as follows

0: 8 0 2, 0 0 2
1: empty
2: 0 2 4
3: empty
4: 0 4 5
5: empty
6: 0 6 6
7: 1 7 0, 0 7 5
8: empty
9: 0 9 0

After arranging it again, it becomes the following sequence

802, 2, 24, 45, 66, 170, 75, 90

Finally, the third grouping (numbers in the hundreds place) is performed again and bucketed

0: 0 02, 0 24, 0 45, 0 66, 0 75, 0 90
1: 1 70
2–7: Empty
8: 8 02
9: Empty

After sorting it out, we found that the entire sequence is already in order.

2, 24, 45, 66, 75, 90, 170, 802

The entire LSD radix sorting process is like this. Of course, different programs can construct different forms of buckets for storing data, but the principle is the same.

LSD radix sort is a fast and stable sorting algorithm. Its time complexity can be expressed as O(Kn). Where n is the number of elements in the sequence to be sorted, and K is the number of digits. How we should understand this K needs to be explained to everyone. Sometimes K can be regarded as a constant-for the above example, K is 3. Because in the above example, the largest number is 802, which has 3 digits. Therefore, in this case, radix sort is more efficient than any comparison sorting algorithm. Because among the comparison sorting algorithms, the time complexity of the optimal sorting algorithm is also O(nlogn).

But in general, K can no longer be considered a constant. So what should K be? Here we take decimal numbers as an example. Each number in the integer sequence is a number with base 10. Let's use b as the base, that is, b=10. If the largest number in the entire integer sequence is N. It is easy to see that K= log _b N. So in general, the time complexity of radix sort can be regarded as O(n log _b N). When N is very large, is the efficiency of radix sort lower than the optimal comparison sorting algorithm (the time complexity of the optimal comparison sorting algorithm is O(nlogn)). Now let's assume that N <= n ^c , where c is a constant. In this case, the time complexity of radix sort becomes O(n log _b n). But even so, it cannot be faster than the comparison sorting algorithm with a complexity of O(nlogn). What if we make the value of b larger? If we make the value of b n, then the time complexity of radix sort becomes linear, that is, O(n). That is to say, if the number of the sequence to be sorted is based on n, then the numbers in the sequence can be between 1 and n ^c . Its time complexity is linear.

Well, let's stop here for the discussion of the efficiency of radix sorting. Next, we should move on to our core issue - the implementation of the LSD radix sorting code.

/**
 * 找到序列中最大位数
 */
function FindMaxBit($arr){
    /*
     * 首先查找序列中最大的数
     */
    $p = $arr[0];
    for($i=1;$i<count($arr);$i++){
        if($arr[$i]>=$p){
            $p = $arr[$i];
        }
    }
    //得到最大的数以后，计算出该数据有多少位
    $d = 1;
    while(floor($p/10)>0){
        $d++;
        $p = floor($p/10);
    }
    return $d;
}
function LSD_RadixSort(&$arr){
    //得到序列中最大位数
    $d = FindMaxBit($arr);
    $bucket = array();
    //初始化队列
    for($i=0;$i<10;$i++){
        $bucket[$i]=array('num'=>0,'val'=>array());
    }
    /*
     * 开始进行分配
     */
    $radix = 1;
    for($i=1;$i<=$d;$i++){
        for($j=0;$j<count($arr);$j++){
            $k = floor($arr[$j]/$radix)%10;
            $bucket[$k]['num']++;
            array_push($bucket[$k]['val'],$arr[$j]);
        }
        $arr = array();
        foreach ($bucket as $key => $val) {
            for ($j = 0; $j < $val['num']; $j ++) {
                $arr[] = $val['val'][$j];
            }
        }
        for($l=0;$l<10;$l++){
            $bucket[$l]=array('num'=>0,'val'=>array());
        }
        $radix *= 10;
    }
}
$arr = array(
    15,77,23,43,90,87,68,32,11,22,33,99,88,66,44,113,
    224,765,980,159,456,7,998,451,96,0,673,82,91,100
);
LSD_RadixSort($arr,0,count($arr)-1);
print_r($arr);

In the above code, I store the actual data directly in the bucket. Then the data in the bucket overwrites the data in the original queue in order. Then the overwritten queues are grouped again and the process continues.

Of course, there is another way, which is to apply for a queue of the same size as the original sequence (it may be a temporary queue), and then apply for an array used as a bucket. The bucket only stores the position of the numbers in the original sequence in the temporary queue, and then put the numbers in the original sequence into the temporary queue according to the order in the bucket. Then assign the entire temporary queue to the original sequence.

Although the two are implemented in different ways, their space complexity is the same. Let's see how to implement the latter in code.

function LSD_RadixSort(&$arr){
    //得到序列中最大位数
    $d = FindMaxBit($arr);
    $bucket = array();
    $temp = array();
    //初始化队列
    for($i=0;$i<10;$i++){
        $bucket[$i] = 0;
    }
    /*
     * 开始进行分配
     */
    $radix = 1;
    for($i=1;$i<=$d;$i++){
        for($j=0;$j<count($arr);$j++){
            $k = floor($arr[$j]/$radix)%10;
            $bucket[$k]++;
        }
        //在桶中调整原序列在临时队列中的位置
        for($j=1;$j<10;$j++){
            $bucket[$j] += $bucket[$j-1];
        }
        for($j=count($arr)-1;$j>=0;$j--){
            $k = floor($arr[$j]/$radix)%10;
            $temp[--$bucket[$k]] = $arr[$j];
        }
        /*
         * 将临时队列赋值给原序列
         */
        for($j=0;$j<count($temp);$j++){
            $arr[$j] = $temp[$j];
        }
        for($j=0;$j<10;$j++){
            $bucket[$j] = 0;
        }
        $radix *= 10;
    }
}

The above is a basic introduction to radix sort. I hope this will be helpful to you.