基本解法
第一步
以LSD为例,假设原来有一串数值如下所示:
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值,在走访数值时将它们分配至编号0到9的桶子中:
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
第二步
接下来将这些桶子中的数值重新串接起来,成为以下的数列:
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配,这次是根据十位数来分配:
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
第三步
接下来将这些桶子中的数值重新串接起来,成为以下的数列:
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕;如果排序的对象有三位数以上,则持续进行以上的动作直至最高位数为止。
LSD的基数排序适用于位数小的数列,如果位数多的话,使用MSD的效率会比较好。MSD的方式与LSD相反,是由高位数为基底开始进行分配,但在分配之后并不马上合并回一个数组中,而是在每个“桶子”中建立“子桶”,将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。
Java实现代码:
package com.algorithm.sort;
import java.util.Arrays;
public class RadixSort {
//基于计数排序的基数排序算法
private static void radixSort(int[] array,int radix, int distance) {
//array为待排序数组
//radix,代表基数
//代表排序元素的位数
int length = array.length;
int[] temp = new int[length];//用于暂存元素
int[] count = new int[radix];//用于计数排序
int divide = 1;
for (int i = 0; i < distance; i++) {
System.arraycopy(array, 0,temp, 0, length);
Arrays.fill(count, 0);
for (int j = 0; j < length; j++) {
int tempKey = (temp[j]/divide)%radix;
count[tempKey]++;
}
for (int j = 1; j < radix; j++) {
count [j] = count[j] + count[j-1];
}
//个人觉的运用计数排序实现计数排序的重点在下面这个方法
for (int j = length - 1; j >= 0; j--) {
int tempKey = (temp[j]/divide)%radix;
count[tempKey]--;
array[count[tempKey]] = temp[j];
}
divide = divide * radix;
}
}
/**
* @param args
*/
public static void main(String[] args) {
int[] array = {3,2,3,2,5,333,45566,2345678,78,990,12,432,56};
radixSort(array,10,7);
for (int i = 0; i < array.length; i++) {
System.out.print(" " + array[i]);
}
}
}
分享到:
相关推荐
快速排序算法结构简单,平均性能较佳; 基数排序性能较稳定。结合快速排序和基数排序,本文提出超快速排序算法,通过理论分析和实验表明,新算法的性能优于快速排序算法和基数排序算法。
经典排序算法之基数排序
详解Java常用排序算法-基数排序
基数排序算法 java实现 还有基数排序的原理文档
基数排序是另一种线性的排序算法,但比起计数排序,更适用于排序的元素比较大的情况,其关键之处在于对于每一位的排序必须使用稳定的排序算法,而计数排序是较好的选择。
算法是基数排序,运行时间只有O(n),比较好。
基数排序算法,这是分不错的算法,实现起来有点难,用静态链表实现,每次改变结点的指向,希望有用,多多指教
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
采用c++描述了各种排序算法,包括选择排序 冒泡排序 插入排序 基数排序 快速排序 归并排序 。实验内容 1、创建排序类。 2、提供操作:选择排序、冒泡排序、插入排序、*基数排序、*快速排序、*归并排序。 3、*能够...
这边所要介绍的「基数排序法」(radix sort)则是属于「分配式排序」(distribution sort),基数排序法又称「桶子法」(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些「桶...
Radix Sort (基数排序)排序算法
十大经典排序算法 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中 进行排序,而外部排序是因排序的数据很大,一次...基数排序等。用一张图概括:
各种排序算法的实现函数:包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。 查找最大最小值函数 findMinMax:在给定数组中查找最大值和最小值。 计算平均值...
该算法用C++语言实现了基数排序算法,已经调试通过,在Linux系统环境中运行结果正常
在这份文档中,我用C语言实现了排序算法的多种方法,包括插入排序、选择排序、冒泡排序、希尔排序、归并排序、快速排序、桶排序和基数排序。这些算法可以帮助我们对数据进行有效的排序和整理,以便更好地处理和分析...
h) 基数排序(选作); i) 其他; 具体要求如下: a) 测试数据分出三类:正序,逆序,随机数据; b) 对于这三类数据,比较上述排序算法中的关键字的比较次数和移动次数; c) 对于这三类数据,比较上述排序算法的执行...
经典排序算法,有选择排序,冒泡排序,交换排序,谢尔排序,插入排序基数排序
这个是在vc6.0下利用递归算法实现的基数排序算法的程序,注释很详细,方便初学者读
基数排序不是基于比较的算法、而是基于统计学角度来观察,此资源包含了基数排序的算法、python代码以及流程图等,欢迎来下载。