经典排序算法 - 基数排序Radix sort
原理类似桶排序,这里总是需要10个桶,多次使用
首先以个位数的值进行装桶,即个位数为1则放入1号桶,为9则放入9号桶,暂时忽视十位数
例如
待排序数组[62,14,59,88,16]简单点五个数字
分配10个桶,桶编号为0-9,以个位数数字为桶编号依次入桶,变成下边这样
| 0 | 0 | 62 | 0 | 14 | 0 | 16 | 0 | 88 | 59 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |桶编号
将桶里的数字顺序取出来,
输出结果:[62,14,16,88,59]
再次入桶,不过这次以十位数的数字为准,进入相应的桶,变成下边这样:
由于前边做了个位数的排序,所以当十位数相等时,个位数字是由小到大的顺序入桶的,就是说,入完桶还是有序
| 0 | 14,16 | 0 | 0 | 0 | 59 | 62 | 0 | 88 | 0 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |桶编号
因为没有大过100的数字,没有百位数,所以到这排序完毕,顺序取出即可
最后输出结果:[14,16,59,62,88]
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
/**
* 基数排序
* 限制:数值只能是正整数
* 算法思想:从低位开始排序,根据排序的结果重新排序
* @author sunlzx
*
*/
public class RadixSort {
public static void main(String[] args) {
//随即生成待排序的数据
int size = 10;
Integer[] nums = new Integer[size];
Random random = new Random();
for (int i = 0; i < nums.length; i++) {
nums[i] = random.nextInt(1000);
}
System.out.println("before:" + Arrays.toString(nums));
//基数排序
radixSort(nums);
System.out.println("after:" + Arrays.toString(nums));
}
public static void radixSort(Integer[] nums) {
int max = getMax(nums);
System.out.println("max : " + max);
int times = 1;
do {
radixSort(nums, times);
times++;
} while (max / (int) Math.pow(10, times - 1) > 0);
}
/**
* 获取待排序中的最大值
* @param nums
* @return
*/
private static int getMax(Integer[] nums) {
int max = 0;
for (Integer i : nums) {
if (i > max) {
max = i;
}
}
return max;
}
/**
*
* @param nums
* @param times 1根据个位排序,2根据百位排序,依次类推
*/
private static void radixSort(Integer[] nums, int times) {
List<Integer>[] buckets = new List[10];
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new ArrayList<Integer>();
}
for (int i = 0; i < nums.length; i++) {
int n = nums[i];
int index = n / (int) Math.pow(10, times - 1) % 10;
buckets[index].add(n);
}
System.out.println(Arrays.toString(buckets));
int index = 0;
for (List<Integer> list : buckets) {
for (Integer integer : list) {
nums[index] = integer;
index++;
}
}
}
}
分享到:
相关推荐
排序算法中的基数排序,更重要的是会算时间复杂度,基数排序可以说是以计数排序位基础的,只不过变成了一位一位来或者一个字节一个字节来,每位或者每个字节都过了一遍,则排序完毕。很简单的程序,在code::block IDE...
Java基数排序Radix Sort原理及用法解析 Java基数排序Radix Sort是一种高效的稳定性排序算法, thuộc於“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort。顾名思义,它是通过键值的...
经典排序算法 – 基数排序Radix sort 原理类似桶排序,这里总是需要10个桶,多次使用 首先以个位数的值进行装桶,即个位数为1则放入1号桶,为9则放入9号桶,暂时忽视十位数 例如 待排序数组[62,14,59,88,16]简单点五个...
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种排序方法对于大数据量的处理非常有效,尤其适合于数据范围远大于内存大小的情况。以下是基数排序的详细...
void radix_sort(int A[],int B[],int length,int d) { int i; for (i=1;i;i++) { get_k(A,B,i,length,d); insert_sort(B,A,length); printf("\n\n第%d位排序完成的结果:\n\n",i); print_A(A,length); ...
基数排序:基数排序(Radix Sort)是一种非比较型的整数排序算法,其基本思想是按照从最低位到最高位的顺序对数字进行排序。基数排序可以用于对整数或字符串进行排序,因为它实际上是对每个数字位进行排序,而不是...
### Radix Sort (基数排序) 排序算法详解 #### 一、算法介绍与应用场景 基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达...
基数排序(Radix Sort)是一种非比较型整数排序算法,其效率高于基于比较的传统排序算法。本文将深入探讨基数排序的基本原理及其程序实现。 #### 基数排序概述 基数排序通过按位对整数进行排序来工作。它首先按照...
经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - 归并排序Merge sort 经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - 选择排序Selection sort 经典排序算法 - ...
基数排序是一种非比较排序算法,其基本思想是将整数按位数切割成不同的数字,然后按每个位数分别进行排序。
基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别进行排序。以下是对基数排序原理及应用的详细解释: 基数排序的原理 1. 数位排序:基数排序从最低位...
基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字拆分成数字位。并且按照数字位的值对数据项进行排序,这种方法不需要进行比较操作。 为了尽可能少的...
**基数排序(Radix Sort)**是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种算法对于大数据量的排序非常有效,尤其是在数据范围较大的情况下,其时间复杂度可以...
在`基数排序Radix_sort.cpp`中,我们可以看到如何利用这个原理实现排序过程。 其次,堆排序是一种基于比较的排序算法,它通过构建一个大顶堆或小顶堆来完成排序。堆是一种特殊的树形数据结构,其每个父节点的值都...
基数排序(Radix Sort)是一种非比较型的整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串、卡片等数据(当成是整数即可),所以基数排序并不限于整数。它是...
1. 计数排序(Counting Sort)基数排序: 计数排序本身是一种非比较型排序,适用于排序非负整数。在基数排序中,我们从最低有效位(个位)开始,到最高有效位(高位)结束。对于每一位,我们创建一个大小为10的数组...
基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如将数字转换为字符串形式),所以基数排序也可以很自然地扩展到...