基数排序算法

作者:原创时间:2022-05-22
文档

排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是基数排序算法:

基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

1. 基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法:

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

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

2. LSD 基数排序动图演示


代码实现

JavaScript

实例

//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;
}

Java

实例

/**
 * 基数排序
 * 考虑负数的情况还可以参考: https://code.i-harness.com/zh-CN/q/e98fa9
 */

public class RadixSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

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

    /**
     * 获取最高位数
     */

    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 (long temp = 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) {
            // 考虑负数的情况,这里扩展一倍队列数,其中 [0-9]对应负数,[10-19]对应正数 (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 (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

    /**
     * 自动扩容,并保存数据
     *
     * @param arr
     * @param value
     */

    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}

PHP

实例

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;
}

C++

实例

int maxbit(int data[], int n) //辅助函数,求数据的最大位数
{
    int maxData = data[0];              ///< 最大数
    /// 先求出最大数,再求其位数,这样有原先依次每个数判断其位数,稍微优化点。
    for (int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData >= p)
    {
        //p *= 10; // Maybe overflow
        maxData /= 10;
        ++d;
    }
    return d;
/*    int d = 1; //保存最大的位数
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(data[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d;*/

}
void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}

C

实例

#include
#define MAX 20
//#define SHOWPASS
#define BASE 10

void print(int *a, int n) {
  int i;
  for (i = 0; i < n; i++) {
    printf("%d ", a[i]);
  }
}

void radixsort(int *a, int n) {
  int i, b[MAX], m = a[0], exp = 1;

  for (i = 1; i < n; i++) {
    if (a[i] > m) {
      m = a[i];
    }
  }

  while (m / exp > 0) {
    int bucket[BASE] = { 0 };

    for (i = 0; i < n; i++) {
      bucket[(a[i] / exp) % BASE]++;
    }

    for (i = 1; i < BASE; i++) {
      bucket[i] += bucket[i - 1];
    }

    for (i = n - 1; i >= 0; i--) {
      b[--bucket[(a[i] / exp) % BASE]] = a[i];
    }

    for (i = 0; i < n; i++) {
      a[i] = b[i];
    }

    exp *= BASE;

#ifdef SHOWPASS
    printf(" PASS   : ");
    print(a, n);
#endif
  }
}

int main() {
  int arr[MAX];
  int i, n;

  printf("Enter total elements (n <= %d) : ", MAX);
  scanf("%d", &n);
  n = n < MAX ? n : MAX;

  printf("Enter %d Elements : ", n);
  for (i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }

  printf(" ARRAY  : ");
  print(&arr[0], n);

  radixsort(&arr[0], n);

  printf(" SORTED : ");
  print(&arr[0], n);
  printf(" ");

  return 0;
}

Lua

实例

-- 获取表中位数
local maxBit = function (tt)
    local weight = 10;      -- 十進制
    local bit = 1;
   
    for k, v in pairs(tt) do
        while v >= weight do
            weight = weight * 10;
            bit = bit + 1;  
        end
    end
    return bit;
end
-- 基数排序
local radixSort = function (tt)
    local maxbit = maxBit(tt);

    local bucket = {};
    local temp = {};
    local radix = 1;
    for i = 1, maxbit do
        for j = 1, 10 do
            bucket[j] = 0;      --- 清空桶
        end
        for k, v in pairs(tt) do
            local remainder = math.floor((v / radix)) % 10 + 1;    
            bucket[remainder] = bucket[remainder] + 1;      -- 每個桶數量自動增加1
        end
       
        for j = 2, 10 do
            bucket[j] = bucket[j - 1] + bucket[j];  -- 每个桶的数量 = 以前桶数量和 + 自个数量
        end
        -- 按照桶的位置,排序--这个是桶式排序,必须使用倒序,因为排序方法是从小到大,顺序下来,会出现大的在小的上面清空。
        for k = #tt, 1, -1 do
            local remainder = math.floor((tt[k] / radix)) % 10 + 1;
            temp[bucket[remainder]] = tt[k];
            bucket[remainder] = bucket[remainder] - 1;
        end
        for k, v in pairs(temp) do
            tt[k] = v;
        end
        radix = radix * 10;
    end
end;

参考地址:

https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/10.radixSort.md

https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F

以下是热心网友对基数排序算法的补充,仅供参考:

热心网友提供的补充1:

java 代码里,mod 每次循环会乘 10,但 counter 的行数是不需要变的,能包含 [-9,9] 就可以了。

for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        // 考虑负数的情况,这里扩展一倍队列数,其中 [0-9]对应负数,[10-19]对应正数 (bucket + 10)
    int[][] counter = new int[20][0];

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

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

热心网友提供的补充2:

艾孜尔江补充使用C#基数排序算法如下:

///基数排序
static void RadixSort(List list)
{
    int maxValue = list.Max();//列表内部方法拿过来用用(在Linq中)
    int it = 0;//需要几趟
                //maxvalue 9-1 99-2 999-3
                //10^0<=9 10^1>9 it=1
                //10^0<99 10^1<99 10^2>99 it=2
    while (Math.Pow(10, it) <= maxValue)
    {
        List> buckets = new List>(10);//分10个桶对应0-9
        for (int i = 0; i < 10; i++)
        {
            buckets.Add(new List());
        }//列表初始化大小
        for (int i = 0; i < list.Count; i++)//入桶
        {
            //989 it=0 989/10^it=989 989%10=9;
            int digit = (int)((list[i]) / (Math.Pow(10, it)) % 10);//得到对应桶
            buckets[digit].Add(list[i]);
        }//全部入桶
        list.Clear();//依次取出来
        for (int i = 0; i < buckets.Count; i++)
        {
            list.AddRange(buckets[i]);
        }
        it += 1;//继续下一次循环入桶出桶
    }
}

热心网友提供的补充3:

补充一下python的基数排序代码实现:

def radix_sort(data):

    if not data:
        return []
    max_num = max(data)  # 获取当前数列中最大值
    max_digit = len(str(abs(max_num)))  # 获取最大的位数

    dev = 1  # 第几位数,个位数为1,十位数为10···
    mod = 10  # 求余数的除法
    for i in range(max_digit):
        radix_queue = [list() for k in range(mod * 2)]  # 考虑到负数,我们用两倍队列
        for j in range(len(data)):
            radix = int(((data[j] % mod) / dev) + mod)
            radix_queue[radix].append(data[j])

        pos = 0
        for queue in radix_queue:
            for val in queue:
                data[pos] = val
                pos += 1

        dev *= 10
        mod *= 10
    return data

热心网友提供的补充4:

go 的补一个吧:

// 基数排序
func RadixSort(arr []int) {
    // 计算最长的数字
    var (
        maxVal int
        maxLen int
    )
    for _, v := range arr {
        if maxVal < v {
            maxVal = v
        }
    }
    for maxVal > 0 {
        maxLen++
        maxVal /= 10
    }

    // 循环进行数据分配与回归
    var (
        base    = 1           // 取余基数,初始是1,用于取出每个元素的倒数第 i+1 位的值,计算公式:v / base %10
        buckets = [10][]int{} // 基数桶,10个
    )
    for i := 0; i < maxLen; i++ { // 遍历位
        for _, v := range arr { // 遍历数组
            d := v / base % 10                 // 每个数字当前位值
            buckets[d] = append(buckets[d], v) // 存入对应桶中
        }

        // 将桶中元素还原到arr
        idx := 0
        for x, bucket := range buckets {
            if len(bucket) == 0 {
                continue
            }

            for _, v := range bucket {
                arr[idx] = v
                idx++
            }

            // 桶清空
            buckets[x] = []int{}
        }

        base *= 10 // 基数*10
    }
}

热心网友提供的补充5:

补上python的实现代码:

def radixSort(nums):
    """
    基数排序,数组元素必须是正整数
    >>>nums = [334, 5, 67, 345, 7, 99, 4, 23, 78, 45, 1, 3453, 23424]
    >>>radixSort(nums)
    >>>[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453, 23424]
    """
    #遍历数组获取数组最大值和最大值对应的位数
    maxValue = nums[0]
    for n in nums:
        maxValue = max(n, maxValue)
    #迭代次数
    iterCount = len(str(maxValue))
    for i in range(iterCount):
        #定义桶,大小为10,对应0-9
        bucket = [[] for _ in range(10)]
        for n in nums:
            index = (n//10**i)%10
            bucket[index].append(n)
        #nums数组清零,并合并桶内元素至nums
        nums.clear()
        for b in bucket:
            nums.extend(b)
        print(nums)
    return nums
nums = [334, 5, 67, 345, 7, 99, 4, 23, 78, 45, 1, 3453, 23424]
radixSort(nums)

热心网友提供的补充6:

上面 Java 版本有点问题:

for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
    // 考虑负数的情况,这里扩展一倍队列数,其中 [0-9]对应负数,[10-19]对应正数 (bucket + 10)
    int[][] counter = new int[mod * 2][0];
....
}

counter 数组的定义,会随着 mod 不断乘 10 变得越来越大。理论上 counter 数组只需要容量为 20 就可以表示负数与正数的所有数字字符。

另外,方法 getMaxDigit 计算数字的最大长度,只考虑到最大值的长度,没有考虑当存在负数时,最小值负数的字符长度也可能是最大的长度。

更新后的版本:

/** 基数排序  */
public class RadixSort  {

  public int[] sort(int[] arr) {

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

  /**   * 获取最高位数   */  private int getMaxDigit(int[] arr) {
    int maxValue = getMaxValue(arr);
    int minValue = getMinValue(arr);
    return Math.max(getNumLength(maxValue), getNumLength(minValue));
  }

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

  private int getMinValue(int[] arr) {
    int minValue = arr[0];
    for (int value : arr) {
      if (minValue > value) {
        minValue = value;
      }
    }
    return minValue;
  }

  protected int getNumLength(long num) {
    if (num == 0) {
      return 1;
    }
    int lenght = 0;
    for (long temp = 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) {
      // 考虑负数的情况,这里扩展一倍队列数,其中 [0-9]对应负数,[10-19]对应正数 (bucket + 10)      int[][] counter = new int[20][0];

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

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

    return arr;
  }

  /**   * 自动扩容,并保存数据   *   * @param arr   * @param value   */  private int[] arrayAppend(int[] arr, int value) {
    arr = Arrays.copyOf(arr, arr.length + 1);
    arr[arr.length - 1] = value;
    return arr;
  }
}
以上为基数排序算法详细介绍,插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点,用一张图概括:

关于时间复杂度

平方阶 (O(n2)) 排序 各类简单排序:直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序;

O(n1+§)) 排序,§ 是介于 0 和 1 之间的常数。 希尔排序

线性阶 (O(n)) 排序 基数排序,此外还有桶、箱排序。

关于稳定性

稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。

名词解释:

n:数据规模

k:"桶"的个数

In-place:占用常数内存,不占用额外内存

Out-place:占用额外内存

稳定性:排序后 2 个相等键值的顺序和排序之前它们的顺序相同

显示全文
排序算法 助人为乐的谚语和名言 春天的谚语 春分的谚语 团结的谚语 帮助人的谚语 谚语的意思 关于关爱的谚语 学习的名言 关于学习的名人名言 关于爱国的名言 陶渊明的名句 激励自己的名言 关于保护环境的名言 叶圣陶的名言 关于家的名言 关于交友的名言警句 有关友谊的名言 关于乐观的名言 列宁的名言 桶排序算法 计数排序算法 堆排序算法 快速排序算法 归并排序算法 希尔排序算法 插入排序算法 选择排序算法 冒泡排序算法 清明的谚语 关于清明的谚语 清明节的谚语 珍惜时间的名言 愁的诗句 含雁的诗句 想念的诗句 牡丹花的诗句 带马字的诗句 关于思念的诗句 描写春天花朵的诗句