`
128kj
  • 浏览: 604109 次
  • 来自: ...
社区版块
存档分类
最新评论

基数排序

阅读更多
    基数排序可以说是扩展了的桶式排序,比如当待排序列在一个很大的范围内,比如0到999999内,那么用桶式排序是很浪费空间的。而基数排序把每个排序码拆成由d个排序码,比如任何一个6位数(不满六位前面补0)拆成6个排序码,分别是个位的,十位的,百位的。。。。
排序时,分6次完成,每次按第i个排序码来排。

下面举一个例子:

   如果要对6个3位整数进行排序,你会怎么做?我猜想大多数人会这样做:
123  123  123 

343  135  135

362  241  241

241  343  343

135  362  352

352  352  362

先对高位进行排序,然后对高位相同的,次高位进行排序,一直进行到低位。

基数排序进行排序的方向一般有两种方式:
1) 高位优先(MSD): 从高位到低位依次对序列排序
2)低位优先(LSD): 从低位到高位依次对序列排序
计算机一般采用低位优先法(人类一般使用高位优先),

低位优先可以按照下面的一组数字做出说明:12、 104、 13、 7、 9

    (1)按个位数排序是12、13、104、7、9

    (2)再根据十位排序104、7、9、12、13

    (3)再根据百位排序7、9、12、13、104

    这里注意,如果在某一位的数字相同,那么排序结果要根据上一轮的数组确定,举个例子来说:07和09在十分位都是0,但是上一轮排序的时候09是排在07后面的;同样举一个例子,12和13在十分位都是1,但是由于上一轮12是排在13前面,所以在十分位排序的时候,12也要排在13前面。

    所以,一般来说,10基数排序的算法应该是这样的?

    (1)判断数据在各位的大小,排列数据;

    (2)根据1的结果,判断数据在十位的大小,排列数据。如果数据在这个位置的余数相同,那么数据之间的顺序根据上一轮的排列顺序确定;

    (3)依次类推,继续判断数据在百位、千位......上面的数据重新排序,直到所有的数据在某一位上数据都为0。

   基数排序一般借助桶式排序,每次按第N位排序时,采用桶式排序。对于如何安排每次落入同一个桶中的数据有两种安排方法:
1)顺序存储:每次使用桶式排序,放入r个桶中,相同时增加计数。
2)链式存储:每个桶通过一个静态队列来跟踪。

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;                  
              
        }  
                  
    }  
  
    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]);  
        }  
          
  
    }  
  
}  

源码下载:
分享到:
评论

相关推荐

    基数排序及流程图

    包括了基数排序的实现代码和流程图。 先对个位数字进行统计,然后根据个位进行排序,然后对十位进行统计,然后根据十位进行排序,即可获得最终结果。 时间效率:待排序列为n个记录,10个关键码,关键码的取值范围为0...

    数据结构基数排序数据结构基数排序

    数据结构中的基数排序是一种非比较型整数排序算法,它基于数字的位宽进行排序,尤其适用于处理大量相同数字的情况。基数排序的核心思想是将数字按照位数从低位到高位分别进行桶排序,最终得到完全有序的序列。下面将...

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

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

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

    这里我们将深入探讨四种常见的排序算法:基数排序、堆排序、希尔排序和直接插入排序。 首先,基数排序是一种非比较型整数排序算法,它的基本思想是将整数按位数切割成不同的数字,然后按每个位数分别比较。基数排序...

    C++写基数排序算法

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。在C++中实现基数排序,主要涉及到数组、计数排序以及位操作等技术。以下是关于基数排序及其C++实现的详细解释...

    基于双向链表的基数排序

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

    基数排序链表法

    基数排序法用链表完成使用C语言适用于刚入门的学者

    数据结构实验报告--链式基数排序算法.doc

    链式基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。在描述中提到的实验报告中,主要目标是实现一个链式基数排序算法,用于对一组数据进行最低位优先的排序...

    Radix Sort (基数排序)排序算法

    ### Radix Sort (基数排序) 排序算法详解 #### 一、算法介绍与应用场景 基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达...

    基数排序-radix sort

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

    基数排序C语言实现

    基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种排序方法非常适合处理大量整数的排序,尤其在数字位数相同或者相差不大的情况下,效率较高。本文将深入...

    数据结构之基数排序数据结构之基数排序数据结构之基数排序

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种排序方法适用于处理大量数据,且数据的范围不超过10的某个幂次方的情况。基数排序是基于多关键字排序的一...

    基数排序算法 java实现

    基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种算法对于大数据量的排序尤其有效,因为其时间复杂度为线性,即O(n*k),其中n是待排序的元素数量,k是每...

    基数排序_C语言_源码_数据结构

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种算法对于大数据量的排序非常有效,尤其是在数据范围不超过0-9的情况下。接下来,我们将深入探讨基数排序...

    基数排序基数排序基数排序

    基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种排序方法不需要进行记录关键字间的比较,而是通过“分配”和“收集”操作对单逻辑关键字进行排序。 1....

    C经典算法之基数排序法

    ### C经典算法之基数排序法 #### 知识点概览 1. **排序算法的基础概念** - 排序算法的基本定义与分类 - 比较性排序与非比较性排序的区别 - 稳定排序与不稳定排序的概念 2. **基数排序的原理** - 分配式排序的...

    基数排序课程设计.rar

    基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这个课程设计主要涵盖了基数排序的基本概念、实现方式以及C++编程技术。在本课程设计中,你将学习到如何用...

    用stl实现基数排序算法

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。它不是基于比较的排序,而是通过创建额外的数据结构,比如计数器或者桶,来达到排序的目的。在处理大量数据时...

    简单的基数排序算法,STL实现

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种算法对于大数据量的排序尤其有效,因为它是线性时间复杂度的,即O(nk),其中n是元素数量,k是数字的最大...

Global site tag (gtag.js) - Google Analytics