精华内容
下载资源
问答
  • 基数排序流程图
    2020-04-29 17:51:18

    基数排序(Radix Sort)

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

    基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。

    算法描述

    • 取得数组中的最大数,并取得位数;
    • arr为原始数组,从最低位开始取每个位组成radix数组;
    • 对radix进行计数排序(利用计数排序适用于小范围数的特点);

    动图演示

     

    代码实现

    int get_digit(int x, int i) {
        while (--i) x /= 10;
        return x % 10;
    }
    
    // 基数排序 需要知道整数的最大位数digits是多少 
    void radix_sort(vector<int> &v, const int &digits) {
        vector<vector<int>> buckets(10);
        int size = v.size();
    
        for (int i = 1; i <= digits; ++i) {
            for (int j = 0; j < 10; ++j) { buckets[j].clear(); }
    
            for (int j = 0; j < size; ++j) {
                buckets[get_digit(v[j], i)].push_back(v[j]);
            }
    
            for(int j = 0, k = 0; j < 10; ++j)
                for(int e : buckets[j])
                    v[k++] = e;
        }
    }

    算法分析

    基数排序基于分别排序,分别收集,所以是稳定的。但基数排序的性能比桶排序要略差,每一次关键字的桶分配都需要O(n)的时间复杂度,而且分配之后收集得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字,则基数排序的时间复杂度将是O(d*2n) ,当然d要远远小于n,因此基本上还是线性级别的。基数排序的空间复杂度为O(n+k),其中k为桶的数量。一般来说n>>k,因此额外空间需要大概n个左右。

    基数排序 vs 计数排序 vs 桶排序

    这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:

    • 基数排序:根据键值的每位数字来分配桶;
    • 计数排序:每个桶只存储单一键值;
    • 桶排序:每个桶存储一定范围的数值;

     

    更多相关内容
  • 基数排序流程图

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

    千次阅读 多人点赞 2022-02-14 19:20:08
    一、什么是基数排序 (1)通过键值得各个位的值,将要排序的元素分配至一些桶中,达到排序的作用 (2)基数排序法是属于稳定性的排序,基数排序法是效率高的稳定排序法 (3)基数排序是桶排序的扩展 二、实现原理 ...

    一、什么是基数排序

    (1)通过键值得各个位的值,将要排序的元素分配至一些桶中,达到排序的作用
    (2)基数排序法是属于稳定性的排序,基数排序法是效率高的稳定排序法
    (3)基数排序是桶排序的扩展

    二、实现原理

            将所有待比较数值(自然数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

    三、实现步骤

    (1)确定数组中的最大元素有几位(MAX)(确定执行的轮数)

    (2)创建0~9个桶(桶的底层是队列),因为所有的数字元素都是由0~9的十个数字组成

    (3)依次判断每个元素的个位,十位至MAX位,存入对应的桶中,出队,存入原数组;直

             至MAX轮结束输出数组。

    (4)具体实现步骤如下图

    四、代码实现

    import java.util.LinkedList;
    
    public class Radix {
    
    	public static void main(String[] args) {
    
    		int[] arr = { 23, 1, 4, 9, 98, 132, 42 };
    
    		sort(arr);
    
    	}
    
    	public static void sort(int[] arr) {
    		// 1.找 分类-收集 的轮数(最大值的长度)
    		int radix = getRadix(arr);
    		// 2.创建桶 list所有桶的集合 每一个桶是LinkedList当成队列来用
    		LinkedList<Integer>[] list = new LinkedList[10];
    		for (int i = 0; i < list.length; i++) {
    			list[i] = new LinkedList<>();
    		}
    		// 3.开始 分类-收集
    		for (int r = 1; r <= radix; r++) {
    			// 分类过程
    			for (int i = 0; i < arr.length; i++) {
    				list[getIndex(arr[i], r)].offer(arr[i]);
    			}
    			int index = 0; // 遍历arr原数组
    			// 收集的过程
    			for (int i = 0; i < list.length; i++) {
    				while (!list[i].isEmpty()) {
    					arr[index++] = list[i].poll();
    				}
    			}
    
    		}
    
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i] + "  ");
    		}
    
    	}
    
    	private static int getIndex(int num, int r) {
    		int ret = 0;
    		for (int i = 1; i <= r; i++) {
    			ret = num % 10;
    			num /= 10;
    		}
    		return ret;
    	}
    
    	private static int getRadix(int[] arr) {
    		int max = arr[0];
    		for (int i = 1; i < arr.length; i++) {
    			if (arr[i] > max) {
    				max = arr[i];
    			}
    		}
    		return (max + "").length();
    	}
    
    }
    

    展开全文
  • 目录 一、基数排序介绍 二、基数排序基本思想 三、基数排序的说明: 看这篇文章很形象 原文链接:https://blog.csdn.net/weixin_42369886/article/details/104875038 一、基数排序介绍 基数排序(radix sort)属于...

    目录

    一、基数排序介绍

    二、基数排序基本思想

    三、基数排序的说明:


    看这篇文章很形象

    原文链接:https://blog.csdn.net/weixin_42369886/article/details/104875038

    一、基数排序介绍


    基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用
    基数排序法是属于稳定性的排序,基数排序法是效率高的稳定性排序法。
    基数排序(Radix Sort)是桶排序的扩展,它是这样实现的:将整数按位数切割成不同的数字,然后按每个位数分别比较。

    二、基数排序基本思想

    将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。这样说明,比较难理解,下面我们看一个图文解释,理解基数排序的步骤。

    将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序。

    第1轮排序 [按照个位排序]:
    说明: 事先准备10个数组(10个桶), 0-9 分别对应 位数的 0-9
    (1) 将 各个数,按照个位大小 放入到 对应的 各个数组中
    (2) 然后从 0-9 个数组/桶中依次按照加入元素的先后顺序取出
    第1轮排序后:542 53 3 14 214 748

    在这里插入图片描述

    第2轮排序 [按照十位排序]
    (1) 将 各个数,按照十位大小 放入到 对应的 各个数组中
    (2) 然后从 0-9 个数组/桶中依次按照加入元素的先后顺序取出
    第2轮排序后: 3 14 214 542 748 53

    在这里插入图片描述 

    第3轮排序 [按照百位排序]
    (1) 将 各个数,按照百位大小 放入到 对应的 各个数组中
    (2) 然后从 0-9 个数组/桶中依次按照加入元素的先后顺序取出
    第3轮排序后:3 14 53 214 542 748 (得到了我们要的顺序) 

    在这里插入图片描述

    代码实现:

      public class RadixSort {
        public static void main(String[] args) {
        int arr[]={53, 3, 542, 748, 14, 214};
        radixSort(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个桶,每个桶就是一个数组
            //为了在放入数时防止数据溢出,我们每个桶的大小为arr.length,即每个桶最多放进数组里的所有元素
            int[][] bucket=new int[10][arr.length];
    
            //定义一个一维数组来记录各个桶的每次放入的数据个数
            int[] bucketElementCount=new int[10];
    
      //第1轮:针对每个元素的个位进行排序处理
            for(int j=0;j<arr.length;j++){
                //取出每个元素的个位进行排序处理
                int digitOfElement=arr[j]/1%10;
                //放入到个位数对应的桶中
                bucket[digitOfElement][bucketElementCount[digitOfElement]]=arr[j];
                bucketElementCount[digitOfElement]++;
            }
            //按照一维数组的下标(即桶的顺序)依次取出数据,放入到原来数组
            int index=0;
            //遍历每一个桶,并将桶中数据放入到原数组
            for(int k=0;k<bucketElementCount.length;k++){
                //如果桶中有数据,才放入原来数组
                if(bucketElementCount[k]!=0){
                    for(int m=0;m<bucketElementCount[k];m++){
                       arr[index++]=bucket[k][m];
                         }
                   }
                   //第一轮处理后,需将bucketElementCount[k]=0
                   bucketElementCount[k]=0;
            }
            System.out.println("第1轮,对个位数的排序处理 arr="+ Arrays.toString(arr));
    
    
    
        //第2轮:针对每个元素的十位进行排序处理
            for(int j=0;j<arr.length;j++){
            //取出每个元素的十位进行排序处理
            int digitOfElement=arr[j]/10%10;
            //放入到个位数对应的桶中
            bucket[digitOfElement][bucketElementCount[digitOfElement]]=arr[j];
            bucketElementCount[digitOfElement]++;
        }
        //按照一维数组的下标(即桶的顺序)依次取出数据,放入到原来数组
         index=0;
        //遍历每一个桶,并将桶中数据放入到原数组
            for(int k=0;k<bucketElementCount.length;k++){
            //如果桶中有数据,才放入原来数组
            if(bucketElementCount[k]!=0){
                for(int m=0;m<bucketElementCount[k];m++){
                    arr[index++]=bucket[k][m];
                }
            }
            //第2轮处理后,需将bucketElementCount[k]=0
            bucketElementCount[k]=0;
          }
            System.out.println("第2轮,对个位数的排序处理 arr="+ Arrays.toString(arr));
    
           //第3轮:针对每个元素的百位进行排序处理
            for(int j=0;j<arr.length;j++){
                //取出每个元素的十位进行排序处理
                int digitOfElement=arr[j]/100%10;
                //放入到个位数对应的桶中
                bucket[digitOfElement][bucketElementCount[digitOfElement]]=arr[j];
                bucketElementCount[digitOfElement]++;
            }
            //按照一维数组的下标(即桶的顺序)依次取出数据,放入到原来数组
            index=0;
            //遍历每一个桶,并将桶中数据放入到原数组
            for(int k=0;k<bucketElementCount.length;k++){
                //如果桶中有数据,才放入原来数组
                if(bucketElementCount[k]!=0){
                    for(int m=0;m<bucketElementCount[k];m++){
                        arr[index++]=bucket[k][m];
                    }
                }
                //第2轮处理后,需将bucketElementCount[k]=0
                bucketElementCount[k]=0;
            }
            System.out.println("第3轮,对个位数的排序处理 arr="+ Arrays.toString(arr));
    
    
        }
    
    }
    

     代码简化:

    public class RadixSort {
        public static void main(String[] args) {
        int arr[]={53, 3, 542, 748, 14, 214};
        radixSort(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个桶,每个桶就是一个数组
            //为了在放入数时防止数据溢出,我们每个桶的大小为arr.length,即每个桶最多放进数组里的所有元素
            int[][] bucket=new int[10][arr.length];
    
            //定义一个一维数组来记录各个桶的每次放入的数据个数
            int[] bucketElementCount=new int[10];
    
            for(int i=0,n=1;i<maxLength;i++,n*=10){
                //对每个元素的对应位进行处理
                for(int j=0;j<arr.length;j++){
                    //取出每个元素的对应位的值
                    int digiOfElement=arr[j]/n%10;
                    //放入到对应的桶中
                    bucket[digiOfElement][bucketElementCount[digiOfElement]]=arr[j];
                    bucketElementCount[digiOfElement]++;
                }
                //按照这个桶的顺序即一维数组的下标一次取出数据放入原来数组
                int index=0;
                //遍历每一桶,并将桶中数据放入到原数组
                for(int k=0;k<bucketElementCount.length;k++){
                    //如果桶中有数据,才放入原来数组
                    if(bucketElementCount[k]!=0){
                        for(int m=0;m<bucketElementCount[k];m++){
                            arr[index++]=bucket[k][m];
                        }
                    }
                    //每一轮处理后,需将bucketElementCount[k]=0
                    bucketElementCount[k]=0;
                }
                System.out.println("第"+(i+1)+"轮,对个位数的排序处理 arr="+ Arrays.toString(arr));
            }
    
        }
    
    }
    

    运行结果:

    在这里插入图片描述

     

    三、基数排序的说明:


    (1)基数排序是对传统桶排序的扩展,速度很快。
    (2)基数排序是经典的空间换时间的方式,占用内存很大, 当对海量数据排序 时,容易造成 OutOfMemoryError 。
    (3)基数排序时稳定的。(注:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,如原始数组为{1,3,2,3,5}经过排序后为{1,2,3,3,5},此时第一个3经过排序后仍然在第二个三的前面,则称这种排序算法是稳定的;否则称为不稳定的)。
    (4)有负数的数组,我们不用基数排序来进行排序。
     

    还可以参考这篇,也很形象,总结下来,1)根据个位数排序一轮,2)根据十位数再排序一轮,3)百位排序。。。。。直到排完为止。

    https://blog.csdn.net/weixin_44537194/article/details/87302788

     

    展开全文
  • 基数排序过程及程序基数排序过程及程序基数排序过程及程序基数排序过程及程序
  • 基数排序-radix sort

    2009-10-29 12:43:24
    基数排序的实现 算法是《数据结构(c语言版)》上的,自己写了实现 c++写的
  • 图解基数排序

    千次阅读 多人点赞 2020-03-15 14:07:00
    基数排序介绍 基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用 基数排序...

    基数排序介绍
    基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用
    基数排序法是属于稳定性的排序,基数排序法是效率高的稳定性排序法
    基数排序(Radix Sort)是桶排序的扩展,它是这样实现的:将整数按位数切割成不同的数字,然后按每个位数分别比较

    基数排序基本思想

    将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。这样说明,比较难理解,下面我们看一个图文解释,理解基数排序的步骤。

    将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序。

    • 第1轮排序 [按照个位排序]:
      说明: 事先准备10个数组(10个桶), 0-9 分别对应 位数的 0-9
      (1) 将 各个数,按照个位大小 放入到 对应的 各个数组中
      (2) 然后从 0-9 个数组/桶中依次按照加入元素的先后顺序取出
      第1轮排序后:542 53 3 14 214 748
      在这里插入图片描述
    • 第2轮排序 [按照十位排序]
      (1) 将 各个数,按照十位大小 放入到 对应的 各个数组中
      (2) 然后从 0-9 个数组/桶中依次按照加入元素的先后顺序取出
      第2轮排序后: 3 14 214 542 748 53
      在这里插入图片描述
    • 第3轮排序 [按照百位排序]
      (1) 将 各个数,按照百位大小 放入到 对应的 各个数组中
      (2) 然后从 0-9 个数组/桶中依次按照加入元素的先后顺序取出
      第3轮排序后:3 14 53 214 542 748 (得到了我们要的顺序)
      在这里插入图片描述

    代码演示:

      public class RadixSort {
        public static void main(String[] args) {
        int arr[]={53, 3, 542, 748, 14, 214};
        radixSort(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个桶,每个桶就是一个数组
            //为了在放入数时防止数据溢出,我们每个桶的大小为arr.length,即每个桶最多放进数组里的所有元素
            int[][] bucket=new int[10][arr.length];
    
            //定义一个一维数组来记录各个桶的每次放入的数据个数
            int[] bucketElementCount=new int[10];
    
      //第1轮:针对每个元素的个位进行排序处理
            for(int j=0;j<arr.length;j++){
                //取出每个元素的个位进行排序处理
                int digitOfElement=arr[j]/1%10;
                //放入到个位数对应的桶中
                bucket[digitOfElement][bucketElementCount[digitOfElement]]=arr[j];
                bucketElementCount[digitOfElement]++;
            }
            //按照一维数组的下标(即桶的顺序)依次取出数据,放入到原来数组
            int index=0;
            //遍历每一个桶,并将桶中数据放入到原数组
            for(int k=0;k<bucketElementCount.length;k++){
                //如果桶中有数据,才放入原来数组
                if(bucketElementCount[k]!=0){
                    for(int m=0;m<bucketElementCount[k];m++){
                       arr[index++]=bucket[k][m];
                         }
                   }
                   //第一轮处理后,需将bucketElementCount[k]=0
                   bucketElementCount[k]=0;
            }
            System.out.println("第1轮,对个位数的排序处理 arr="+ Arrays.toString(arr));
    
    
    
        //第2轮:针对每个元素的十位进行排序处理
            for(int j=0;j<arr.length;j++){
            //取出每个元素的十位进行排序处理
            int digitOfElement=arr[j]/10%10;
            //放入到个位数对应的桶中
            bucket[digitOfElement][bucketElementCount[digitOfElement]]=arr[j];
            bucketElementCount[digitOfElement]++;
        }
        //按照一维数组的下标(即桶的顺序)依次取出数据,放入到原来数组
         index=0;
        //遍历每一个桶,并将桶中数据放入到原数组
            for(int k=0;k<bucketElementCount.length;k++){
            //如果桶中有数据,才放入原来数组
            if(bucketElementCount[k]!=0){
                for(int m=0;m<bucketElementCount[k];m++){
                    arr[index++]=bucket[k][m];
                }
            }
            //第2轮处理后,需将bucketElementCount[k]=0
            bucketElementCount[k]=0;
          }
            System.out.println("第2轮,对个位数的排序处理 arr="+ Arrays.toString(arr));
    
           //第3轮:针对每个元素的百位进行排序处理
            for(int j=0;j<arr.length;j++){
                //取出每个元素的十位进行排序处理
                int digitOfElement=arr[j]/100%10;
                //放入到个位数对应的桶中
                bucket[digitOfElement][bucketElementCount[digitOfElement]]=arr[j];
                bucketElementCount[digitOfElement]++;
            }
            //按照一维数组的下标(即桶的顺序)依次取出数据,放入到原来数组
            index=0;
            //遍历每一个桶,并将桶中数据放入到原数组
            for(int k=0;k<bucketElementCount.length;k++){
                //如果桶中有数据,才放入原来数组
                if(bucketElementCount[k]!=0){
                    for(int m=0;m<bucketElementCount[k];m++){
                        arr[index++]=bucket[k][m];
                    }
                }
                //第2轮处理后,需将bucketElementCount[k]=0
                bucketElementCount[k]=0;
            }
            System.out.println("第3轮,对个位数的排序处理 arr="+ Arrays.toString(arr));
    
    
        }
    
    }
    

    代码简化:

    public class RadixSort {
        public static void main(String[] args) {
        int arr[]={53, 3, 542, 748, 14, 214};
        radixSort(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个桶,每个桶就是一个数组
            //为了在放入数时防止数据溢出,我们每个桶的大小为arr.length,即每个桶最多放进数组里的所有元素
            int[][] bucket=new int[10][arr.length];
    
            //定义一个一维数组来记录各个桶的每次放入的数据个数
            int[] bucketElementCount=new int[10];
    
            for(int i=0,n=1;i<maxLength;i++,n*=10){
                //对每个元素的对应位进行处理
                for(int j=0;j<arr.length;j++){
                    //取出每个元素的对应位的值
                    int digiOfElement=arr[j]/n%10;
                    //放入到对应的桶中
                    bucket[digiOfElement][bucketElementCount[digiOfElement]]=arr[j];
                    bucketElementCount[digiOfElement]++;
                }
                //按照这个桶的顺序即一维数组的下标一次取出数据放入原来数组
                int index=0;
                //遍历每一桶,并将桶中数据放入到原数组
                for(int k=0;k<bucketElementCount.length;k++){
                    //如果桶中有数据,才放入原来数组
                    if(bucketElementCount[k]!=0){
                        for(int m=0;m<bucketElementCount[k];m++){
                            arr[index++]=bucket[k][m];
                        }
                    }
                    //每一轮处理后,需将bucketElementCount[k]=0
                    bucketElementCount[k]=0;
                }
                System.out.println("第"+(i+1)+"轮,对个位数的排序处理 arr="+ Arrays.toString(arr));
            }
    
        }
    
    }
    

    运行结果:
    在这里插入图片描述

    基数排序的说明:
    (1)基数排序是对传统桶排序的扩展,速度很快。
    (2)基数排序是经典的空间换时间的方式,占用内存很大, 当对海量数据排序 时,容易造成 OutOfMemoryError 。
    (3)基数排序时稳定的。(注:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,如原始数组为{1,3,2,3,5}经过排序后为{1,2,3,3,5},此时第一个3经过排序后仍然在第二个三的前面,则称这种排序算法是稳定的;否则称为不稳定的)。
    (4)有负数的数组,我们不用基数排序来进行排序。

    展开全文
  • 设计快速排序,堆排序和基数排序的算法。 (2)实验原理: 快速排序:在待排序的n个数据中,任取一个数据为基准,经过一次排序后以基准数据把全部数据分为两部分,所有数值比基准数小的都排在其前面,比它大的都排...
  • 基数排序

    2021-05-23 08:45:51
    C++radix sort基数排序的实现算法完整源码(定义,实现,main函数测试)#include///forcollectionoffunctions#include///foramacrocalledassertwhichcanbeusedtoverifyassumptions#include算法学习笔记4 基数排序2021-...
  • 1)基数排序的核心思想,就是利用特定位(比如个位)统计0--9的个数,然后用累加和数组c倒桶入help,最后转移到arr,完成排序 2)难,是难了点,但是这种桶排序的思想,就是这样,烦,面试官没有特殊要求,不要玩桶...
  • 基数排序(Radix Sort)是桶排序的扩展,它的基本思想是:将整数按位数切割成不同的数字,然后按每个位数分别比较。 具体做法是:将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,...
  • 基本介绍 基数排序(radix sort)的思想是多关键字排序...基数排序示意: 执行流程 下面通过一个例子来体会基数排序过程。 原始序列:80, 43, 155, 987, 100, 31, 6, 299, 155, 0 0)初始桶 每个关键字的每一位都是由
  • 基数排序就这么简单

    2021-03-16 21:32:37
    一、基数排序(桶排序)介绍来源360百科:基数排序(radix sort)属于"分配式排序"(distribution sort),又称"桶子法"(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些"桶"中,藉...
  • 基数排序,图解

    千次阅读 2016-10-30 22:15:43
    基数排序其实是利用队列先进先出的特点,然后进行排序的。基本方法是这样: int arr[] = {278,109,63,930,589,184,505,269,8,83}; 1.初始化十个(数组元素的个数)队列bucket,并存放在一个数组中; 2.求base,即数组...
  • 排序算法 1、内部排序:指将需要处理的的所有数据都需要加载到内部存储中进行排序 2、外部排序:数据量过大,无法将全部加载到内存中,需要借助外部存储进行排序 冒泡排序 介绍 通过从前往后遍历序列,依次比较...
  • 基数排序算法

    2022-07-10 16:49:25
    本章介绍排序算法中的基数排序。内容包括: 1. 基数排序介绍 2. 基数排序图文说明 3. 基数排序实现 3.1 基数排序C实现 3.2 基数排序C++实现 3.3 基数排序Java实现转载请注明出处:基数排序 - 如果天空不死 - 博客园...
  • 【排序】图解基数排序

    千次阅读 多人点赞 2019-02-19 11:47:56
    基数排序可以看成是桶排序的扩展,以整数排序为例,主要思想是将整数按位数划分,准备 10 个桶,代表 0 - 9,根据整数个位数字的数值将元素放入对应的桶中,之后按照输入赋值到原序列中,依次对十位、百位等进行同样...
  • 十大经典排序算法-堆排序,计数排序,桶排序,基数排序 1-堆排序 算法思想: 算法图解: 示例代码: 在这里插入代码片 复杂度分析: 2-计数排序 算法思想: 算法图解: 示例代码: 在这里插入代码片 复杂度分析: 3-桶排序 ...
  • c++排序之基数排序
  • 基数排序算法.zip

    2019-10-30 13:58:25
    基数排序不是基于比较的算法、而是基于统计学角度来观察,此资源包含了基数排序的算法、python代码以及流程图等,欢迎来下载。
  • 基数排序 定义: 基数排序(Radix Sort)是桶排序的扩展,它的基本思想是:将整数按位数切割成不同的数字,然后按每个位数分别比较。 具体做法是:将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。...
  • 一:希尔排序 ...流程如下: 3.步骤 3.1.初始化步长为元素个数的一半 3.2.开始循环,循环至步长为0 3.3开始做插入排序,具体在代码中详解 4.代码区 //希尔排序 void shellSort(int *a, int len) {
  • 基数排序适合于有不同位数的大小数字,例如以下数列: 核心思想是: 先找十个桶:0~9 第一轮按照元素的个位数排序 桶内分别存放上述数组元素的个位数,按照数组元素的顺序依次存放 之后,按照从左向右,从上到下的...
  • 基数排序 基数排序的思想 ​ 将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从个位开始依次进行排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。 图解基数排序 ​ ...
  • *问题描述:设计一个基数排序的算法,将一组英文单词,按字典顺序排列。假设单词均由小写字母或空格构成,最长的单词有MaxLen个字母。 */ 程序及代码 #include #include #include #define MaxLen
  • 基数排序不同于前面的几种排序方式,前面介绍的排序方法或多或少的是通过使用比较和移动来实现排序,而基数排序的实现不需要进行对关键字进行比较,只需要对关键字进行“分配”与“收集”两种操作即可完成。...
  • 概念 基数排序(radix sort)属于稳定性的排序...核心算法流程图 核心算法代码 //基数排序方法 public static void radixSort(int[] arr) { //根据前面的推导过程,我们可以得到最终的基数排序代码 //1. 得

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,003
精华内容 3,601
关键字:

基数排序流程图