devbox
Guff_9hys
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

排序算法 - 桶排序、计数排序、基数排序（线性排序算法）_桶排序 计数排序 基数排序

作者：Guff_9hys | 2024-07-07 06:02:08

赞

踩

桶排序 计数排序 基数排序

目录

1、桶排序(Bucket Sort)

2、计数排序(Counting Sort)

3、基数排序(Radix Sort)

    醒目一点：  

 

    桶排序、计数排序、基数排序可以看作是线性排序算法（Linear Sort），从时间复杂度看远高于归并、快排等，但是这些排序算法对数据的要求非常高，并不能作为常规的排序算法。即特别是类似开发一个排序工具类，需要适应所以特征的数据的排序，显然是不行的。对于这三种排序算法本身并不难，重要的是理解的掌握其大致的应用场景，当遇到类似场景时可以使用。

1、桶排序(Bucket Sort)

    桶排序的思想比较类似散列表，排序前需要对所有数据全部遍历一遍，获取到排序字段的数据区间（最大、最小值），再对排序字段分成K个桶，那么每个桶内存储的排序字段区间就定了。把待排序的数据字段散列到多个有序的桶中，再对每个桶中的数据进行排序，如果桶中的数据个数比较少那可以使用插入排序，否则可以使用快速排序。并且桶排序比较适合的场景是外部排序，即数据量比较大不能一次性加载到内存中进行排序。

    比如：我们需要对50G的订单数据按照金额字段进行排序（比如需要对非常庞大的学生数据按照成绩进行排序），那么这么多数据一定是存储在磁盘上，排序过程肯定涉及到大量的磁盘IO读写操作，并且排序完成后的结果也需要写入磁盘。

    假设服务器的内存为16G，那么我们假设最多可以将10G的数据进行排序。对于50G的数据我们需要 bucket = 50  / 10 = 5个桶进行，此时需要分批次将磁盘中的数据加载到内存中全部遍历一遍，并且记录金额字段的最小和最大值，比如最小金额为 0【比如有赠送的商品价格为0】，最大金额为50000。那么每个有序桶存储存储的金额区间就固定了，(50000 - 0) / 10 = 5000，将50000区间均摊到10个桶的区间【【0-5000】、【5000-10000】、...、【45000-50000】】。

    遍历所有数据将金额分到对应有序的桶中，再对每个桶中的数据使用快速排序，最后再将每个本来就有序的桶进行合并，就得到了想要的结果。我们假设数据会均摊落在对应的桶区间上，但是有可能有些桶中数据为空，有些桶数据量远超我们预定的桶的size，那么此时可以对这个桶本身再次进行桶排序（也算是分治的思想）。

    桶排序的最坏情况就是将所有的数据基本都落到了同一个桶中，极端情况下排序算法的时间复杂度退化为桶内的排序的时间复杂度，如果此时是插入排序则最坏时间复杂度为O(N²)，如果此时使用的是快排则最坏时间复杂度为O(N*logN)。

  1. public class BucketSort {
  2.  
  3.     public static void main(String[] args) {
  4.         /*int[] array = new int[1000];
  5.         Random random = new Random();
  6.         for (int i = 0; i < array.length; i++) {
  7.             array[i] = random.nextInt(100);
  8.         }*/
  9.  
  10.         int[] array = new int[]{14,18,58,98,95,24,35,72,47,31,9,56,48,21,4,8,79,9,52,34,83,95,17,71,39,27,33,53,54,88,76,43,99,97,98,19,35,43,11,11,19,11,8,85,99,42,60,90,45,71,34,91,16,80,73,20,17,77,80,52,51,93,73,1,91,71,20,28,3,31,49,58,12,47,22,8,51,41,3,1,49,94,41,26,87,11,38,53,45,92,43,95,39,79,80,41,86,64,4,82,22,47,70,92,4,62,91,40,72,94,3,67,37,97,44,55,91,82,88,80,51,36,8,5,69,52,80,47,60,27,55,33,44,61,25,20,97,69,36,50,69,89,98,38,70,88,3,8,45,31,86,12,7,42,21,92,54,50,19,79,25,28,28,40,66,27,60,88,97,46,84,77,62,6,8,89,60,32,18,39,81,28,82,45,61,97,45,69,50,35,7,98,62,83,19,4,80,47,5,95,2,64,55,34,60,28,59,20,19,72,18,81,41,27,86,55,61,6,41,3,95,84,69,58,29,65,88,60,29,63,1,66,83,21,54,69,35,45,53,15,15,9,74,45,40,29,19,10,67,83,63,36,88,69,12,33,35,2,60,85,26,68,4,15,23,5,64,46,26,35,27,11,25,10,83,80,32,74,68,39,11,23,34,93,95,66,14,98,84,9,2,19,38,46,77,28,56,80,77,40,10,68,53,78,23,80,15,18,89,18,71,81,81,8,38,69,76,3,45,93,89,6,34,38,58,89,1,36,53,15,42,20,70,66,19,58,42,22,72,74,8,53,62,79,62,22,44,93,68,40,6,10,60,74,61,49,41,37,85,90,69,58,65,65,31,14,44,1,79,52,21,61,97,67,46,67,44,33,35,89,3,12,5,90,14,92,86,45,20,46,82,48,82,47,40,92,28,32,1,37,20,11,27,19,3,36,87,40,52,6,75,85,16,53,94,43,96,60,5,21,34,79,23,54,47,25,3,49,6,56,2,70,58,62,24,39,26,67,60,67,74,41,88,44,55,17,88,7,80,67,78,2,96,34,95,26,84,21,80,39,96,70,83,10,98,58,86,86,75,14,79,94,15,53,71,38,82,2,60,57,36,64,74,28,73,33,25,46,80,57,33,99,87,10,36,58,78,86,17,71,90,39,90,87,17,62,59,29,46,58,66,93,18,76,52,10,94,90,30,0,41,13,53,1,91,48,52,39,44,74,55,36,30,20,46,73,82,80,84,15,89,46,78,99,80,38,64,42,31,19,18,74,98,12,33,77,39,68,40,48,86,87,6,55,20,31,18,95,72,68,43,69,43,90,59,83,92,67,90,25,99,97,44,47,3,22,31,98,51,65,44,13,34,76,65,28,99,73,24,52,12,70,39,90,75,26,15,18,56,82,99,6,42,24,26,43,92,71,69,96,44,33,24,14,51,14,89,84,0,42,18,21,71,85,0,67,18,38,48,18,15,39,42,31,77,36,66,35,37,40,55,77,66,78,63,99,52,4,0,67,66,78,13,31,87,57,62,80,47,2,67,41,96,35,16,93,24,69,73,85,18,49,47,11,48,21,22,24,67,54,40,93,58,13,9,23,30,7,34,72,51,62,51,98,81,41,63,19,50,27,2,27,63,89,15,54,14,30,17,42,63,77,1,33,83,43,97,39,7,30,79,76,94,5,98,85,25,89,1,98,99,94,39,95,84,48,2,24,38,29,0,7,27,64,13,64,30,11,31,25,49,30,9,40,11,37,38,7,19,88,69,82,33,50,54,63,77,67,16,91,9,98,67,81,69,88,58,57,23,3,65,48,54,92,21,11,62,44,36,94,13,62,16,38,97,94,44,38,47,1,58,3,5,1,5,7,52,60,43,82,21,54,20,64,40,51,41,78,72,0,59,64,50,85,1,71,78,8,57,41,64,58,83,10,14,98,35,29,16,32,41,28,4,67,0,90,73,40,96,17,0,27,85,31,94,63,48,13,1,82,41,14,49,47,51,22,15,81,29,44,33,57,34,22,93,63,52,88,4,66,95,91,79,42,96,13,53,24,45,59,37,77,79,7,90,3,99,31,13,58,31,74,34,26,12,94,44,18,73,8,61,54,64,9,65,1,9,41,91,63,57,26,11,53,8,86,60,3,14,42,31,0,44,41,89,36,83,37,56,73,55,25,28,42,5,86,1,40,72,95,56,20,83,74,86,46,20,25,97,38,84,35,2,45,34,68,49,10,41,82,37,74,70,43,12,37,85,72,20,55,21,12,63,88,19,82,84,24,79,23};
  11.  
  12.         System.out.println("排序前：" + Arrays.toString(array));
  13.         bucketSort(array, 10);
  14.         System.out.println("排序后：" + Arrays.toString(array));
  15.     }
  16.  
  17.     /**
  18.      * 桶排序
  19.      * 从代码的嵌套情况看， 没有 冒泡、选择、插入排序那样的 for for嵌套的情况，则不存在 O(N²) 的情况
  20.      * 虽然使用了多次的单 for循环，但是整体趋势上是接近 O(N) 的时间复杂度
  21.      *
  22.      * @param array 待排序数据
  23.      * @param bucketSize 桶容量
  24.      */
  25.     public static void bucketSort(int[] array, int bucketSize) {
  26.         if (array.length < 2) {
  27.             return;
  28.         }
  29.  
  30.         // 记录需要排序的最大最小值
  31. //        boolean isAsc = array[0] >= array[1];
  32. //        int minValue = isAsc ? array[1] : array[0];
  33. //        int maxValue = isAsc ? array[0] : array[1];
  34.  
  35.         // 数组最小值
  36.         int minValue = array[0];
  37.         // 数组最大值
  38.         int maxValue = array[1];
  39.  
  40.         // 遍历一遍数据，确定数据的范围
  41.         for (int i = 0; i < array.length; i++) {
  42.             if (array[i] < minValue) {
  43.                 minValue = array[i];
  44.             } else if (array[i] > maxValue) {
  45.                 maxValue = array[i];
  46.             }
  47.         }
  48.  
  49.         // 计算桶个数
  50.         int bucketCount = (maxValue - minValue) / bucketSize + 1;
  51.         int[][] buckets = new int[bucketCount][bucketSize];
  52.         int[] indexArray = new int[bucketCount];
  53.  
  54.         // 将数值中的值分配到每个桶
  55.         for (int i = 0; i < array.length; i++) {
  56.             int bucketIndex = (array[i] - minValue) / bucketSize;
  57.             if (indexArray[bucketIndex] == buckets[bucketIndex].length) {
  58.                 ensureCapacity(buckets, bucketIndex);
  59.             }
  60.             buckets[bucketIndex][indexArray[bucketIndex]++] = array[i];
  61.         }
  62.  
  63.         // 对每个桶（二位数组）进行排序，这里使用快排
  64.         int k = 0;
  65.         for (int i = 0; i < buckets.length; i++) {
  66.             // 可能存在桶没有数据的情况
  67.             if (indexArray[i] == 0) {
  68.                 continue;
  69.             }
  70.             // 使用快排对当前的桶内元素进行排序
  71.             QuickSort.quickSortInternally(buckets[i], 0, indexArray[i] - 1);
  72.             for (int j = 0; j < indexArray[i]; j++) {
  73.                 array[k++] = buckets[i][j];
  74.             }
  75.         }
  76.     }
  77.  
  78.     /**
  79.      * 两倍进行扩容进行扩容
  80.      * 当数据分布不均匀时，可能出现当前位置的桶的容量不够的情况，则进行两倍扩容
  81.      *
  82.      * @param buckets 桶数据
  83.      * @param bucketIndex 当前桶的位置
  84.      */
  85.     private static void ensureCapacity(int[][] buckets, int bucketIndex) {
  86.         int[] tmp = buckets[bucketIndex];
  87.         // 申请新的两倍容量的数组
  88.         int[] newArray = new int[tmp.length * 2];
  89.         // 将原数据放到新数组的前面， 放完正好是容器的一半位置
  90.         for (int i = 0; i < tmp.length; i++) {
  91.             newArray[i] = tmp[i];
  92.         }
  93.         // 将桶数据替换为新数组
  94.         buckets[bucketIndex] = newArray;
  95.     }
  96.  
  97. }

 

2、计数排序(Counting Sort)

    计算排序的使用场景是需要排序的字段基本都落在了比较少的一部分区间，并且每个排序字段值可能出现多次。比如我们经常形容高考就是1分可以压倒几万人，类似这样的场景我们就可以使用计数排序进行解决。理解了桶排序是将排序字段分成多个排序区间，那么我们也可以将计数排序理解成桶排序的一种极端情况，每个桶中只有一个值。计数排序还要求排序的字段是一个非负整数，所以如果要对包含了负数的字段进行计数排序，则可以将其转换为正整数再进行排序。比如排序字段区间是[-10,10]，那么就可以对排序字段整体加10然后再进行排序，最后的排序结构没有影响。

    下面是计数排序的代码，需要说明，其中非常重要的一步就是对每个位置出现的个数需要叠加到后一个位置出现的个数上面，目的就是让出排序的下标位置。比如：1出现了3次，2出现了5次，3出现了6次；那么叠加完成后1 -> 3；2 -> 8；3对应14。我们再将原数组从尾进行遍历，很明显所有排序好之后，3出现的对应下标位置就是【41-1-6，14-1】，非常巧妙。  

  1. /**
  2.  *  计数排序
  3.  *  计算排序可以理解是特殊的桶排序，对数据的要求更苛刻
  4.  *  数据要求：数据的范围根据密集，并且范围尽可能的小，比如下面模拟数据十万的数据出现在100的范围内，
  5.  *           那么计数【桶缩小到1，当前也不用再执行快排了】的平均出现次数是1000.
  6.  *
  7.  * @author kevin
  8.  * @date 2021/2/22 15:25
  9.  * @since 1.0.0
  10.  */
  11. public class CountingSort {
  12.  
  13.     public static void main(String[] args) {
  14.         // 创建模拟数据，十万的数据，区间在100 之内， 很可能某个数都出现多次【平均每个位置出现1000次】，所以是计数排序
  15.         int[] array = new int[100000];
  16.         Random random = new Random();
  17.         for (int i = 0; i < 100000; i++) {
  18.             array[i] = random.nextInt(100);
  19.         }
  20.  
  21.         System.out.println("排序前：" + Arrays.toString(array));
  22.         countingSort(array);
  23.         System.out.println("排序后：" + Arrays.toString(array));
  24.     }
  25.  
  26.     /**
  27.      *  计数排序
  28.      * @param array 待排序数组
  29.      */
  30.     public static void countingSort(int[] array) {
  31.         if (array.length < 2) {
  32.             return;
  33.         }
  34.  
  35.         // 确认待查询的数据的范围
  36.         int maxValue = array[0];
  37.         for (int i = 0; i < array.length; i++) {
  38.             if (maxValue < array[i]) {
  39.                 maxValue = array[i];
  40.             }
  41.         }
  42.  
  43.         // 申请一个最大数的数组空间,并且初始化计数全是0
  44.         int[] count = new int[maxValue + 1];
  45.         for (int i = 0; i < maxValue; i++) {
  46.             count[i] = 0;
  47.         }
  48.  
  49.         // 计算每个元素出现的次数
  50.         for (int i = 0; i < array.length; i++) {
  51.             // array[i]的值本身就是count的下标 每次++
  52.             count[array[i]]++;
  53.         }
  54.  
  55.         // 依次累加，这个很关键，主要用于处理后续的拷贝数据的下标位置
  56.         for (int i = 1; i <= maxValue; i++) {
  57.             // 0和1加的值给1 1和2加的值给2【1的值本身就是前面加后的结果】 最后count[maxValue]的值就是所有之和
  58.             count[i] = count[i - 1] + count[i];
  59.         }
  60.  
  61.         // 申请临时数组存储排序后的结果
  62.         int[] tmp = new int[array.length];
  63.         for (int i = array.length - 1; i >= 0; i--) {
  64.             // array[最大下标]就是获取原数组中的值，count[原数组中的值]就获取到大概位置上的个数
  65.             // 比如第一次的下标为 99999 的原始数据为45， 那么就是获取所有值中1-45的个数 46230 为 index（数组的下标是从0开始的，所以需要index值需要 - 1）
  66.             int index = count[array[i]] - 1;
  67.             // 将原数组中的值赋值给 tmp[46230]
  68.             tmp[index] = array[i];
  69.             // 那么当前应该把 下标为45的统计个数给减去1
  70.             // 下次再获取到值为45时， tmp下标就为 56230 - 1 了，排到了该值的前一位，所以是稳定排序
  71.             count[array[i]]--;
  72.         }
  73.  
  74.         // 将结果拷贝到原数组
  75.         for (int i = 0; i < array.length; i++) {
  76.             array[i] = tmp[i];
  77.         }
  78.     }
  79.  
  80. }

3、基数排序(Radix Sort)

    基数排序使用的场景根据严苛，比如我们需要将20完牛津字典按照字母进行排序，或者我们需要将一大堆的电话号码按照从小到大的顺序进行排序。这类数据有一个特点就是如果排序的前一位已经在前面了，后面的位置就没有必要进行比较了。比如：

abc和bac，第一位上面 abc的a 比 bac的b排在前面，那第二位即使 abc的b 比 bac的a排在后面也没有用。而排序的思想如果是字母就是取字符串的第一位进行比较，然后再取第二位进行比较；如果是电话号码就直接对电话号码本身取余 ...10000，1000,100,10等。       

    另外基数排序的基数（位数）不能太大，否则根据基数排序的时间复杂度是O(N*K)，K过大时基数排序就已经不是线性排序了。因为我们在第一位不能进行完全排序的情况下，则需要对第二位进行的一轮排序。比如英语的长度大概都在十多位，即基本在排序十多轮就完成了排序；电话号码为11位数，那么K值为11。

下面是对电话号码进行排序的实现：

  1. public class RadixSort {
  2.  
  3.     public static void main(String[] args) {
  4.         // 使用电话号码模拟
  5.         long[] array = new long[]{13811125683L, 13856569891L, 15856985695L, 17769699897L,
  6.             18965659692L, 15984653263L, 19965654254L, 13454879652L
  7.         };
  8.  
  9.         System.out.println("排序前：" + Arrays.toString(array));
  10.         radixSort(array);
  11.         System.out.println("排序后：" + Arrays.toString(array));
  12.     }
  13.  
  14.     /**
  15.      * 基数排序
  16.      * @param array 待排序数组
  17.      */
  18.     public static void radixSort(long[] array) {
  19.         if (array.length < 2) {
  20.             return;
  21.         }
  22.  
  23.         long maxValue = array[0];
  24.         for (int i = 0; i < array.length; i++) {
  25.             if (array[i] > maxValue) {
  26.                 maxValue = array[i];
  27.             }
  28.         }
  29.  
  30.         // 从个位开始，对数组array按 指数进行排序： 1，10， 100，1000
  31.         for (int exp = 1; maxValue / exp > 0; exp *= 10) {
  32.             // 对每位上进行排序
  33.             countingSort(array, exp);
  34.         }
  35.     }
  36.  
  37.     /**
  38.      * 对每一位上进行排序
  39.      * @param array 待排序数组
  40.      * @param exp 除数，也就觉得了是排哪个位
  41.      */
  42.     public static void countingSort(long[] array, int exp) {
  43.         if (array.length < 2) {
  44.             return;
  45.         }
  46.  
  47.         // 计算每个元素的个数
  48.         int[] count = new int[10];
  49.         for (int i = 0; i < array.length; i++) {
  50.             // 比如电话号码是 13800000000 / 100000000 就是比较百位， 取余就是为了放入计数叠加器
  51.             count[(int)((array[i] / exp) % 10)]++;
  52.         }
  53.  
  54.         // 计算排序后的位置, 叠加计算出后面的位置下标，具体可以参见计数排序的注释
  55.         for (int i = 1; i < count.length; i++) {
  56.             count[i] = count[i - 1] + count[i];
  57.         }
  58.  
  59.         // 申请临时数组
  60.         long[] tmp = new long[array.length];
  61.         for (int i = array.length - 1; i >= 0; i--) {
  62.             tmp[count[(int)((array[i] / exp) % 10)] - 1] = array[i];
  63.             count[(int)((array[i] / exp) % 10)]--;
  64.         }
  65.  
  66.         // 重置排序后的结果
  67.         for (int i = 0; i < array.length; i++) {
  68.             array[i] = tmp[i];
  69.         }
  70.     }
  71. }

 

 

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号