排序算法学习笔记（三）

秒速五厘米 2023-09-29 14:03 35阅读 0赞

**目录**

一：基数排序

二：常用排序算法总结和对比

--------------------

## 一：基数排序 ##

**1.1 概念：**

>  *  基数排序属于“分配式排序”，又称“桶子法”（bucketSort），它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。
>  *  基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法。
>  *  基数排序是桶排序的拓展。
>  *  基数排序是1887年赫尔曼.何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。

**1.2 代码演示：**

public class RadixSortDemo {
        public static void main(String[] args) {
            /*
            int[] arr={53,3,542,748,14,214};
            System.out.println("排序前的数组："+Arrays.toString(arr));
    
            radixSort(arr);
            System.out.println("第一轮排序结果："+ Arrays.toString(arr));
    
            RadixSort(arr);
            System.out.println("基数排序后的数组："+Arrays.toString(arr));
            */
    
            //基数排序算法执行时间测试:
            int[] arr=new int[80000];
            for(int i=0;i<arr.length;i++){
                arr[i]=Math.round(100000);
            }
            long time1 = System.currentTimeMillis();
            RadixSort(arr);
            long time2 = System.currentTimeMillis();
            System.out.println((time2-time1));
            
            //基数排序算法执行时间：12ms
    
    
    
        }
        //基数排序方法
    
        //根据第一轮，可以推导出规律
        public static void RadixSort(int[] arr){
            //1.先得到数组中最大的数的位数：
            int max=arr[0];//假设第一数就是最大数
            for(int i=1;i<arr.length;i++){
                max=Math.max(max,arr[i]);
            }
    
            //得到最大数是几位数
            int maxLength=(max+"").length();
    
    
            int[][] bucket=new int[10][arr.length];
            int[] bucketElementCounts=new int[10];
    
            for(int q=0,n=1;q<maxLength;q++,n*=10){
                //针对每个元素的对应位进行排序处理
                for(int j=0;j<arr.length;j++){
                    //取出位的值
                    int digitOfElement=arr[j]/n%10;
                    //放入到对应的桶中
                    bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[j];
                    bucketElementCounts[digitOfElement]++;
                }
    
                //按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）
                int index=0;
                //遍历每一桶，并将桶中的元素，放入原数组，每次遍历完，要把bucketElementCounts【k】清零
                for(int k=0;k<bucketElementCounts.length;k++){
                    //如果桶中有数据，我们才放入到数组中
                        //循环该桶即第k个桶（即第k个一维数组），放入
                        for(int l=0;l<bucketElementCounts[k];l++){
                            //取出元素放入到arr
                            arr[index++]=bucket[k][l];
                        }
                    //每轮处理后，需要将每个bucketElementCounts[k]=0！！！
                    bucketElementCounts[k]=0;
                }
            }
    
    
        }
    
        public static void radixSort(int[] arr){
            //第1轮（针对每个元素的个位进行排序处理）
    
            //定义一个二维数组，表示10个桶，每个桶就是一个一维数组
            //说明：
            //1.二维数组包含10个一维数组
            //2.为了防止在放入数的时候，数据溢出，则每个一维数组（桶），大小定为arr.length
            //3.名明确，基础排序是使用空间换时间的经典算法
            int[][] bucket=new int[10][arr.length];
    
            //为了记录每个桶中，实际存放了多少个数据，我们定义一个一维数组来记录各个桶的每次放入的数据个数
            //可以这样理解
            //比如：bucketElementCounts[0],记录的就是bucket[0]桶的放入数据个数
            int[] bucketElementCounts=new int[10];
    
            //第一轮（针对每个元素的个位进行排序处理）
            for(int j=0;j<arr.length;j++){
                //取出每个元素的个位的值
                int digitOfElement=arr[j]%10;
                //放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[j];
                bucketElementCounts[digitOfElement]++;
            }
    
            //按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）
            int index=0;
            //遍历每一桶，并将桶中的元素，放入原数组
            for(int k=0;k<bucketElementCounts.length;k++){
                //如果桶中有数据，我们才放入到数组中
                    //循环该桶即第k个桶（即第k个一维数组），放入
                    for(int l=0;l<bucketElementCounts[k];l++){
                        //取出元素放入到arr
                        arr[index++]=bucket[k][l];
                    }
    
                //第一轮处理后，需要将每个bucketElementCounts[k]=0！！！
                bucketElementCounts[k]=0;
            }
    
    
        }
    }

**1.3 图形演示：**

![在这里插入图片描述][20191225164306488.gif]

（该图像来自于[Java 排序算法之基数排序\_笑看烟雨红尘的博客-CSDN博客][Java _-CSDN]中的照片，纯属方便记忆，无商业作用）。

**1.4 基数排序算法的说明：**

>  *  基数排序是对传统桶排序的扩张，速度很快。
>  *  基数排序是经典的空间换时间的方式，占用内存很大，当对海量数据排序时，容易造成OutofMemoryError。
>  *  基数排序是稳定的【注：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r\[i\]=r\[j\],且r\[i\]在r\[j\]之前，而在排序后的序列中,r\[i\]仍在r\[j\]之前，则称这种个排序算法是稳定的；否则称是不稳定的】

## 二：常用排序算法总结和对比 ##

![a3e2663b73e44e38bf8fd7f6d293f264.png][]

![1b6ea7e627644937b34f9f982ad39bb2.png][]

[20191225164306488.gif]: https://img-blog.csdnimg.cn/20191225164306488.gif
[Java _-CSDN]: https://blog.csdn.net/qq_39249094/article/details/103701828
[a3e2663b73e44e38bf8fd7f6d293f264.png]: https://img-blog.csdnimg.cn/a3e2663b73e44e38bf8fd7f6d293f264.png
[1b6ea7e627644937b34f9f982ad39bb2.png]: https://img-blog.csdnimg.cn/1b6ea7e627644937b34f9f982ad39bb2.png