十大排序算法之基数排序

2017-03-25

本文总阅读量0次

(1)算法简介

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

(2)算法描述和实现

具体算法描述如下：

<1>.取得数组中的最大数，并取得位数；
<2>.arr为原始数组，从最低位开始取每个位组成radix数组；
<3>.对radix进行计数排序（利用计数排序适用于小范围数的特点）；

Javascript代码实现：

**
 * 基数排序适用于：
 *  (1)数据范围较小，建议在小于1000
 *  (2)每个数值都要大于等于0
 * @author xiazdong
 * @param  arr 待排序数组
 * @param  maxDigit 最大位数
 */
//LSD Radix Sort
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    var counter = [];
    console.time('基数排序耗时');
    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;
                }
          }
        }
    }
    console.timeEnd('基数排序耗时');
    return arr;
}
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(radixSort(arr,2)); //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

php代码实现:

#基数排序,此处仅对正整数进行排序，至于负数和浮点数，需要用到补码，各位有兴趣自行研究
   #计数排序
   #@param $arr 待排序数组
   #@param $digit_num 根据第几位数进行排序
   function counting_sort(&$arr, $digit_num = false) {
     if ($digit_num !== false) { #如果参数$digit_num不为空，则根据元素的第$digit_num位数进行排序
       for ($i = 0; $i < count($arr); $i++) {
         $arr_temp[$i] = get_specific_digit($arr[$i], $digit_num);
       }
     } else {
       $arr_temp = $arr;
     }
     $max = max($arr);
     $time_arr = array(); #储存元素出现次数的数组
     #初始化出现次数数组
     for ($i = 0; $i <= $max; $i++) {
       $time_arr[$i] = 0;
     }
     #统计每个元素出现次数
     for ($i = 0; $i < count($arr_temp); $i++) {
       $time_arr[$arr_temp[$i]]++;
     }
     #统计每个元素比其小或相等的元素出现次数
     for ($i = 0; $i < count($time_arr) - 1; $i++) {
       $time_arr[$i + 1] += $time_arr[$i];
     }
     #利用出现次数对数组进行排序
     for($i = count($arr) - 1; $i >= 0; $i--) {
       $sorted_arr[$time_arr[$arr_temp[$i]] - 1] = $arr[$i];
       $time_arr[$arr_temp[$i]]--;
     }
     $arr = $sorted_arr;
     ksort($arr);  #忽略这次对key排序的效率损耗
   }
   #计算某个数的位数
   function get_digit($number) {
     $i = 1;
     while ($number >= pow(10, $i)) {
      $i++;
     }
     return $i;
   }
   #获取某个数字的从个位算起的第i位数
   function get_specific_digit($num, $i) {
     if ($num < pow(10, $i - 1)) {
       return 0;
     }
     return floor($num % pow(10, $i) / pow(10, $i - 1));
   }
   #基数排序,以计数排序作为子排序过程
   function radix_sort(&$arr) {
     #先求出数组中最大的位数
     $max = max($arr);
     $max_digit = get_digit($max);
     for ($i = 1; $i <= $max_digit; $i++) {
       counting_sort($arr, $i);
     }
   }
   $arr = array(23,0,32,45,56,75,43,0,34);
   radix_sort($arr);
   var_dump($arr);

(3)算法分析

最佳情况：T(n) = O(n k)
最差情况：T(n) = O(n k)
平均情况：T(n) = O(n * k)

基数排序有两种方法：

MSD 从高位开始进行排序
LSD 从低位开始进行排序

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶
计数排序：每个桶只存储单一键值
桶排序：每个桶存储一定范围的数值