`

基数排序(Radix Sort)

 
阅读更多

 

经典排序算法 - 基数排序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++;
			}
		}

	}

}

分享到:
评论

相关推荐

    基数排序radix sort

    排序算法中的基数排序,更重要的是会算时间复杂度,基数排序可以说是以计数排序位基础的,只不过变成了一位一位来或者一个字节一个字节来,每位或者每个字节都过了一遍,则排序完毕。很简单的程序,在code::block IDE...

    Java基数排序radix sort原理及用法解析

    Java基数排序Radix Sort原理及用法解析 Java基数排序Radix Sort是一种高效的稳定性排序算法, thuộc於“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort。顾名思义,它是通过键值的...

    c#基数排序Radix sort的实现方法

    经典排序算法 – 基数排序Radix sort 原理类似桶排序,这里总是需要10个桶,多次使用 首先以个位数的值进行装桶,即个位数为1则放入1号桶,为9则放入9号桶,暂时忽视十位数 例如 待排序数组[62,14,59,88,16]简单点五个...

    基数排序-radix sort

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种排序方法对于大数据量的处理非常有效,尤其适合于数据范围远大于内存大小的情况。以下是基数排序的详细...

    基数排序——radix-sort

    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)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达...

    基数排序原理和程序Radix Sort Tutorial

    基数排序(Radix Sort)是一种非比较型整数排序算法,其效率高于基于比较的传统排序算法。本文将深入探讨基数排序的基本原理及其程序实现。 #### 基数排序概述 基数排序通过按位对整数进行排序来工作。它首先按照...

    经典算法的C#源码实现

    经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - 归并排序Merge sort 经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - 选择排序Selection sort 经典排序算法 - ...

    matlab 实现基数排序(Radix Sort)

    基数排序是一种非比较排序算法,其基本思想是将整数按位数切割成不同的数字,然后按每个位数分别进行排序。

    基数排序的原理及应用.pdf

    基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别进行排序。以下是对基数排序原理及应用的详细解释: 基数排序的原理 1. 数位排序:基数排序从最低位...

    基于双向链表的基数排序

    基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字拆分成数字位。并且按照数字位的值对数据项进行排序,这种方法不需要进行比较操作。 为了尽可能少的...

    radix sort

    **基数排序(Radix Sort)**是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种算法对于大数据量的排序非常有效,尤其是在数据范围较大的情况下,其时间复杂度可以...

    基数排序、堆排序、希尔排序、直接插入排序

    在`基数排序Radix_sort.cpp`中,我们可以看到如何利用这个原理实现排序过程。 其次,堆排序是一种基于比较的排序算法,它通过构建一个大顶堆或小顶堆来完成排序。堆是一种特殊的树形数据结构,其每个父节点的值都...

    基数排序过程及程序基数排序过程及程序

    基数排序(Radix Sort)是一种非比较型的整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串、卡片等数据(当成是整数即可),所以基数排序并不限于整数。它是...

    基数排序_RADIXSORT

    1. 计数排序(Counting Sort)基数排序: 计数排序本身是一种非比较型排序,适用于排序非负整数。在基数排序中,我们从最低有效位(个位)开始,到最高有效位(高位)结束。对于每一位,我们创建一个大小为10的数组...

    基数排序代码.docx

    基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如将数字转换为字符串形式),所以基数排序也可以很自然地扩展到...

Global site tag (gtag.js) - Google Analytics