江苏网站建设哪家专业,百科网站怎么做,青岛有什么网络科技有限公司,芸志建站怎么建立网站1 基本介绍
1.1 概述
#xff08;1#xff09;基数排序#xff08;radix sort#xff09;属于“分配式排序”#xff0c;顾名思义#xff0c;它是通过键值的各个位的值#xff0c;将要排序的元素分配至某些“桶”中#xff0c;达到排序的作用。 #xff08;2#x…1 基本介绍
1.1 概述
1基数排序radix sort属于“分配式排序”顾名思义它是通过键值的各个位的值将要排序的元素分配至某些“桶”中达到排序的作用。 2基数排序是属于稳定性的排序基数排序法是效率高的稳定性排序法。 3基数排序是桶排序的扩展。 4基数排序是1887年赫尔曼.何乐礼发明的。它是这样实现的将整数按位数切割成不同的数字然后按每个位数分别比较。
1.2 算法详解
首先基数排序是根据数位来进行排序的。它是从个位开始然后按照每一位的数进行排序如下图所示: 排完序之后就往前进一位然后再将所有的数按照这一位所在的数进行排序如下图所示: 重复这个过程直到所有的位数都已经被排过序了。如下图所示 并且如果这个过程中碰到某个数在这个为上没有数的话就进行补零操作将该位看成是0。就比方下图用红框圈出来的部分 等到所有的位数都已经排序完毕之后就可以看到已经排序好的序列了。
这个过程很好理解但是如果是第一次看这个算法的肯定会有一个的困惑那就是为什么基数排序选择的是从低位到高位来进行排序的而不是像平常比较数据的大小一样从高位到低位来比较呢?
这里先不讲为什么先看下面这两个案例
从高位到低位进行比较
原序列百位排好序后十位排好序后个位排好序后329839657839457720457329657657355657839457839457436436436436720329720355355355329720
从低位到高位进行比较
原序列个位排好序后十位排好序后百位排好序后329720720329457355329355657436436436839457839457436657355657720329457720355839655839
对比看了上面两个例子之后相信大家就知道了很明显如果是从高到低位来进行比较的话会发现比较到最后之后序列仍然是无序的但是从低位到高位进行比较的话就会发现序列到最后已经排好序了。
是不是很奇怪同样的执行过程只不过执行的顺序发生了改变为什么结果就回产生这样的结果呢产生这个差异的重点就是在我们忽略了一个问题那就是在进行高位到低位比较的时候高位的权重是高于低位的。就比方下图所示 正是因为这个原因所以采取的是从低位到高位比较的过程.
说完基本思想之后,来说一下算法的实现步骤:
第一次遍历序列.找出序列中的最大值MAX找到MAX之后可以确定需要比较多少数位了。这时候就需要按照元素在该位数对应的数字将元素存入到相应的容器之中。如下图所示 之后再按照容器的顺序将元素重新弹出构成接下来需要排序的序列如下图所示 最后只需要重复23步骤直到最高位也比较完毕那么整个基数排序就已经完成了。
算法图解
2 代码实现
/*** 基数排序*/
public class RadixSort {public static void main(String[] args) {int[] arr {53, 3, 542, 478, 14, 241, 2, 23};radixSort(arr);System.out.println(Arrays.toString(arr));}// 基数排序方法public static void radixSort(int[] arr) {// 得到数组中最大的数的位数int max arr[0];for (int i 1; i arr.length; i) {if (arr[i] max) {max arr[i];}}// 得到最大数的位数决定循环几轮int maxLength (max ).length();// 定义一个二维数组表示10个桶每个桶就是一个一维数组// 说明// 1. 二维数组包含10个一维数组// 2. 为了防止在放入数的时候数据溢出则每一个一维数组(桶)大小定为 arr.length// 3. 明确基数排序是使用空间换时间的经典算法int[][] bucket new int[10][arr.length];// 为了记录每个桶中实际存放了多少个数据定义一个一维数组来记录各个桶的每次放入的数据个数int[] bucketElementCounts new int[10];// 循环 maxLength 轮for (int i 0, n 1; i maxLength; i, n * 10) {// 针对每个元素的对应位进行排序for (int j 0; j arr.length; j) {// 取出每个元素的对应位的值int digitOfElement arr[j] / n % 10;// 放入到对应的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]] arr[j];bucketElementCounts[digitOfElement];}// 按照这个桶的顺序依次取出数据放入到原来数组int index 0;for (int k 0; k bucketElementCounts.length; k) {// 如果桶中有数据放入到原数组if(bucketElementCounts[k] ! 0){// 循环该桶即第k个桶放入for (int l 0; l bucketElementCounts[k]; l) {arr[index] bucket[k][l];}}// 第 i1 轮处理后需要将每个 bucketElementCounts[k]0bucketElementCounts[k] 0;}System.out.println(第 (i1) 轮对位数的排序处理 arr Arrays.toString(arr));}}
}
3 复杂度分析
时间复杂度 基数排序只需要根据最大元素的位数遍历相应次数的序列即可所以可以确定基数排序的时间复杂度一定是线性级别的虽然是线性级别的但是有一个系数的这个系数就是最大元素的位数K所以时间复杂度应该是O(n*k)。空间复杂度 空间复杂度主要取决于链表的数量以及序列元素的数量所以空间复杂度为O(nk)。
