算法入门教程-基数排序

上节我们学习了归并排序,我们知道了归并采用的是分治的策略,在分的过程中采用的是递归来处理,而治的过程才是我们算法的核心,更多详解看算法入门教程-归并排序,这节我们学习另外一种算法:基数排序,首先我们简单的介绍下什么是基数排序?

基数排序

官方介绍:基数排序称为"分配式排序",有称"桶子法"通过键值的各个位的值,将要排序的元素分配到某些"桶"中来达到排序的作用.

基数排序属于稳定性排序,同样也是桶排序的扩展

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

接下来我们通过图解的方式来理解上述所描述的过程:
假设我待排序的数列为{53,3,542,748,14,214},我们来看具体过程:

• 第一轮的图解过程:

第一轮排序过程.png

• 第二轮的图解过程

  
  第二轮排序过程.png

• 第三轮图解过程

  
  第三轮排序结果图.png

通过三轮的排序我们最终完成了排序过程,图中有具体的详细,这里我简单的补充说明下为啥什么这样存放

• 首先图中0-9代表10个一位数组(也就是我们的桶)
• 其中我们元素取到的个位和十位以及百位等值,对应的就是我们下标为0-9的一维数组

这样大家可能明白许多了,我们接着通过代码的方式来实现

代码实现过程

假设我待排序的列表为:{53,3,542,748,14,214}

• 公用代码

//基数排序方法
public static void radixSort(int[] arr){
    //首先我们来定义一个二维数组来表示10个桶,其中每个桶就是一个一维数组
    //为了防止放入元素的时候溢出,这里将每个桶的大小定为arr.length
    //基数排序是经典的空间换取时间的算法
    int [][] bucket = new int[10][arr.length];
    //为了统计每个桶中实际的元素的个数,这里定义一个一维数组来记录每次放入元素的个数
    //如:bucketEleCounts[0]表示记录的是bucket[0]桶的放入元素的个数
    int [] bucketEleCounts = new int[10];

• 第一轮排序代码实现

 //第一轮:针对每一个元素的个位进行排序处理
    for (int j = 0; j <arr.length ; j++) {
        //取出每个元素的个位数
        int digitOfElement = arr[j] %10;
        //放入到对应的桶中
        //说明:
        // bucket[digitOfElement]表示第几个桶;因为我们计算出来的个位数也代表它是第几个桶
        //[bucketEleCounts[digitOfElement]]表示对应桶的元素
        bucket[digitOfElement][bucketEleCounts[digitOfElement]] = arr[j];
        // ++ 操作表示如果后面计算得到个位数相同的话,我们需要将它放入已有元素的后面
        bucketEleCounts[digitOfElement] ++;
    }
    //2.按照上述桶的顺序,我们将一维数组的下标依次取出该元素放入到原数组(arr)
    //首先定义一个临时索引index
    int index = 0;
    //遍历操作
    for (int k = 0; k <bucket.length ; k++) {
        //如果我们的桶中有数据,才放入到原数组中
        if (bucketEleCounts[k] !=0){
            //循环该桶,也就是第K个桶
            for (int l = 0; l <bucketEleCounts[k] ; l++) {
                //将第k个桶的第l个元素放入到原数组中
                arr[index] = bucket[k][l];
                index ++;
            }
        }
        //注意:
        //第一轮处理完过后,我们需要将每一个(bucketEleCounts[k]清零,为了后面步骤的需要
        bucketEleCounts[k] = 0;
    }

    System.out.println("第一轮对个位的排序处理结果");
    System.out.println(Arrays.toString(arr));

• 来看测试代码

/**
 * 算法学习-基数排序
*/
public class RadixSort {
public static void main(String[] args) {

    int [] arr = {53,3,542,748,14,214};
    radixSort(arr);

• 测试结果如图:

  
  第一轮测试结果.png

• 第二轮排序代码实现

//第二轮:针对每一个元素的个位进行排序处理
    for (int j = 0; j <arr.length ; j++) {
        //取出每个元素的十位数
        int digitOfElement = arr[j] /10 %10;
        //放入到对应的桶中
        //说明:
        // bucket[digitOfElement]表示第几个桶;因为我们计算出来的个位数也代表它是第几个桶
        //[bucketEleCounts[digitOfElement]]表示对应桶的元素
        bucket[digitOfElement][bucketEleCounts[digitOfElement]] = arr[j];
        // ++ 操作表示如果后面计算得到个位数相同的话,我们需要将它放入已有元素的后面
        bucketEleCounts[digitOfElement] ++;
    }
    //2.按照上述桶的顺序,我们将一维数组的下标依次取出该元素放入到原数组(arr)
    //首先定义一个临时索引index
     index = 0;
    //遍历操作
    for (int k = 0; k <bucket.length ; k++) {
        //如果我们的桶中有数据,才放入到原数组中
        if (bucketEleCounts[k] !=0){
            //循环该桶,也就是第K个桶
            for (int l = 0; l <bucketEleCounts[k] ; l++) {
                //将第k个桶的第l个元素放入到原数组中
                arr[index] = bucket[k][l];
                index ++;
            }
        }
        //注意:
        //第二轮处理完过后,我们需要将每一个(bucketEleCounts[k]清零,为了后面步骤的需要
        bucketEleCounts[k] = 0;
    }

    System.out.println("第二轮对个位的排序处理结果");
    System.out.println(Arrays.toString(arr));

• 直接看测试结果如图所示:

  
  第二轮测试结果图.png

• 第三轮排序代码实现

   //第三轮:针对每一个元素的个位进行排序处理
    for (int j = 0; j <arr.length ; j++) {
        //取出每个元素的十位数
        int digitOfElement = arr[j] /100 %10;
        //放入到对应的桶中
        //说明:
        // bucket[digitOfElement]表示第几个桶;因为我们计算出来的个位数也代表它是第几个桶
        //[bucketEleCounts[digitOfElement]]表示对应桶的元素
        bucket[digitOfElement][bucketEleCounts[digitOfElement]] = arr[j];
        // ++ 操作表示如果后面计算得到个位数相同的话,我们需要将它放入已有元素的后面
        bucketEleCounts[digitOfElement] ++;
    }
    //2.按照上述桶的顺序,我们将一维数组的下标依次取出该元素放入到原数组(arr)
    //首先定义一个临时索引index
    index = 0;
    //遍历操作
    for (int k = 0; k <bucket.length ; k++) {
        //如果我们的桶中有数据,才放入到原数组中
        if (bucketEleCounts[k] !=0){
            //循环该桶,也就是第K个桶
            for (int l = 0; l <bucketEleCounts[k] ; l++) {
                //将第k个桶的第l个元素放入到原数组中
                arr[index] = bucket[k][l];
                index ++;
            }
        }
        //注意:
        //第二轮处理完过后,我们需要将每一个(bucketEleCounts[k]清零,为了后面步骤的需要
        bucketEleCounts[k] = 0;
    }

    System.out.println("第三轮对个位的排序处理结果");
    System.out.println(Arrays.toString(arr));
}

• 测试结果如下图所示:

  
  第三轮测试结果图.png

通过三轮的处理我们最终完成了排序,我们来整合下代码

//基数排序方法
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];
    //为了统计每个桶中实际的元素的个数,这里定义一个一维数组来记录每次放入元素的个数
    //如:bucketEleCounts[0]表示记录的是bucket[0]桶的放入元素的个数
    int [] bucketEleCounts = new int[10];

    //整合代码
    for (int i = 0,  n=1; i < maxLength ; i++, n *=10) {
        //每一轮:针对每一个元素的对应位进行排序处理; 第一轮是个位,第二轮是十位,第三轮是百位....
        for (int j = 0; j <arr.length ; j++) {
            //取出每个元素的对应位的值
            int digitOfElement = arr[j] /n %10;
            //放入到对应的桶中
            //说明:
            // bucket[digitOfElement]表示第几个桶;因为我们计算出来的个位数也代表它是第几个桶
            //[bucketEleCounts[digitOfElement]]表示对应桶的元素
            bucket[digitOfElement][bucketEleCounts[digitOfElement]] = arr[j];
            // ++ 操作表示如果后面计算得到个位数相同的话,我们需要将它放入已有元素的后面
            bucketEleCounts[digitOfElement] ++;
        }
        //2.按照上述桶的顺序,我们将一维数组的下标依次取出该元素放入到原数组(arr)
        //首先定义一个临时索引index
        int index = 0;
        //遍历操作
        for (int k = 0; k <bucket.length ; k++) {
            //如果我们的桶中有数据,才放入到原数组中
            if (bucketEleCounts[k] !=0){
                //循环该桶,也就是第K个桶
                for (int l = 0; l <bucketEleCounts[k] ; l++) {
                    //将第k个桶的第l个元素放入到原数组中
                    arr[index] = bucket[k][l];
                    index ++;
                }
            }
            //注意:
            //第i+1轮处理完过后,我们需要将每一个(bucketEleCounts[k]清零,为了后面步骤的需要
            bucketEleCounts[k] = 0;
        }

        System.out.println("第"+(i+1)+"轮对个位的排序处理结果");
        System.out.println(Arrays.toString(arr));

    }

• 测试一把结果如图所示:

整合后的测试结果图.png

最后一点我们来测试下基数排序的执行时间效率:

int [] arr = new int[10000000];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int)(Math.random() * 10000000); //随机生成[0,100000)的数
    }

    Date date1 = new Date();
    SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String format = dateFormat.format(date1);
    System.out.println("排序前的时间为:"+format);
    //进行排序
    int [] temp = new int[arr.length];
  radixSort(arr);
    Date date2 = new Date();
    SimpleDateFormat dateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String format2 = dateFormat.format(date2);
    System.out.println("排序后的时间为:"+format2);

• 来看测试结果如图所示:

时间测试.png

可以看出10W条数据排序是没有任何压力的,那么关于基数排序的学习就到这了...