排序算法系列：基数排序

全栈程序员-站长 • 2026年3月18日下午10:07 • 未分类 • 阅读 1

引言

今天要说的这个排序算法很特殊，它不需要直接对元素进行相互比较，也不需要将元素相互交换，你需要做的就是对元素进行“分类”。这也是基数排序的魅力所在，基数排序可以理解成是建立在“计数排序”的基础之上的一种排序算法。在实际项目中，如果对效率有所要求，而不太关心空间的使用时，我会选择用计数排序（当然还有一些其他的条件），或是一些计数排序的变形。

版权说明

著作权归作者所有。
商业转载请联系作者获得授权，非商业转载请注明出处。
本文作者：Q-WHai
发表日期： 2016年6月16日
本文链接：https://qwhai.blog.csdn.net/article/details/
来源：CSDN
更多内容：分类 >> 算法与数学

基数排序

数据背景

排序原理

上面说到基数排序不需要进行元素的比较与交换。如果你有一些算法的功底，或者丰富的项目经验，我想你可能已经想到了这可能类似于一些“打表”或是哈希的做法。而计数排序则是打表或是哈希思想最简单的实现。

计数排序

基数排序原理图

算法优化

算法实现

import org.algorithm.array.sort.interf.Sortable; / *  * 基数排序/桶排序 * 
 * 2016年1月19日 * * @author Q-WHai * @see http://blog.csdn.net/lemon_tree12138 * @version 0.1.1 */ public class RadixSort implements Sortable { 
      @Override public int[] sort(int[] array) { 
      if (array == null) { 
      return null; } int maxLength = maxLength(array); return sortCore(array, 0, maxLength); } private int[] sortCore(int[] array, int digit, int maxLength) { 
      if (digit >= maxLength) { 
      return array; } final int radix = 10; // 基数 int arrayLength = array.length; int[] count = new int[radix]; int[] bucket = new int[arrayLength]; // 统计将数组中的数字分配到桶中后，各个桶中的数字个数 for (int i = 0; i < arrayLength; i++) { 
      count[getDigit(array[i], digit)]++; } // 将各个桶中的数字个数，转化成各个桶中最后一个数字的下标索引 for (int i = 1; i < radix; i++) { 
      count[i] = count[i] + count[i - 1]; } // 将原数组中的数字分配给辅助数组 bucket for (int i = arrayLength - 1; i >= 0; i--) { 
      int number = array[i]; int d = getDigit(number, digit); bucket[count[d] - 1] = number; count[d]--; } return sortCore(bucket, digit + 1, maxLength); } /* * 一个数组中最大数字的位数 * * @param array * @return */ private int maxLength(int[] array) { 
      int maxLength = 0; int arrayLength = array.length; for (int i = 0; i < arrayLength; i++) { 
      int currentLength = length(array[i]); if (maxLength < currentLength) { 
      maxLength = currentLength; } } return maxLength; } /* * 计算一个数字共有多少位 * * @param number * @return */ private int length(int number) { 
      return String.valueOf(number).length(); } /* * 获取 x 这个数的 d 位数上的数字 * 比如获取 123 的 0 位数,结果返回 3 * * @param x * @param d * @return */ private int getDigit(int x, int d) { 
      int a[] = { 
      1, 10, 100, 1000, 10000, , , , ,  }; return ((x / a[d]) % 10); } }

基数排序过程图

复杂度分析

排序方法	时间复杂度			空间复杂度	稳定性	复杂性
	平均情况	最坏情况	最好情况
基数排序	O(d*(n+r))	O(d*(n+r))	O(d*(n+r))	O(n+r)	稳定	较复杂

其中，d 为位数，r 为基数，n 为原数组个数。在基数排序中，因为没有比较操作，所以在复杂上，最好的情况与最坏的情况在时间上是一致的，均为 O(d * (n + r))。

Ref

《算法导论》

GitHub Download

https://github.com/qwhai/algorithms-sort

征集

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/211574.html原文链接：https://javaforall.net

排序算法系列：基数排序

引言

版权说明

基数排序

数据背景