基数排序也称桶排序，是一种当关键字为整数类型时非常高效的排序方法。基数排序算法的基本思想是：设待排序的数据元素关键字是m位d进制整数（不满足的关键字在高位补0），设置d个桶，令其编号分别为0，1，2，…，d-1。首先，按关键字最低位的数值依次把各数据元素放到响应的桶中；然后按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素；这样，就形成了数据元素集合的一个新的排列，称这样的一次排序过程为一次基数排序。再对一次基数排序得到的数据元素序列按关键字次低位的数值依次把各数据放到相应的桶中，然后按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素。这样的过程重复进行，当完成了第m次基数排序后，就得到了排好序的数据元素序列。