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

排序算法之 计数排序 桶排序 基数排序_计数排序的效率要高于任何以比较为基础的排序算法。

作者：我家小花儿 | 2024-07-07 06:51:15

赞

踩

计数排序的效率要高于任何以比较为基础的排序算法。

1.计数排序：Counting Sort

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出，它的优势在于在对于较小范围内的整数排序。它的复杂度为Ο(n+k)（其中k是待排序数的最大值），快于任何比较排序算法，缺点就是非常消耗空间。很明显，如果而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序，比如堆排序和归并排序和快速排序。

算法原理： 
基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一个位置上，在代码中作适当的修改即可。

用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。

算法步骤： 
（1）找出待排序的数组中最大的元素； 
（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项； 
（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）； 
（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

时间复杂度：Ο(n+k)。

空间复杂度：Ο(k)。

要求：待排序数中最大数值不能太大。最大值确定并且不大，必须是正整数。 

稳定性：稳定。

 

计数排序需要占用大量空间，它仅适用于数据比较集中的情况。比如 [0~100]，[10000~19999] 这样的数据。

计数排序的基本思想是：对每一个输入的元素arr[i]，确定小于 arr[i] 的元素个数。
所以可以直接把 arr[i] 放到它输出数组中的位置上。假设有5个数小于 arr[i]，所以 arr[i] 应该放在数组的第6个位置上。

 

计数排序用到一个额外的计数数组C，根据数组C来将原数组A中的元素排到正确的位置。

　　通俗地理解，例如有10个年龄不同的人，假如统计出有8个人的年龄不比小明大（即小于等于小明的年龄，这里也包括了小明），那么小明的年龄就排在第8位，通过这种思想可以确定每个人的位置，也就排好了序。当然，年龄一样时需要特殊处理（保证稳定性）：通过反向填充目标数组，填充完毕后将对应的数字统计递减，可以确保计数排序的稳定性。

 

计数排序属于线性排序，它的时间复杂度远远大于常用的比较排序。（计数是O(n)，而比较排序不会超过O(nlog2nJ)）。

其实计数排序大部分很好理解的，唯一理解起来很蛋疼的是为了保证算法稳定性而做的数据累加，大家听我说说就知道了：

1、首先，先取出要排序数组的最大值，假如我们的数组是int[] arrayData = { 2, 4, 1, 5, 6, 7, 4, 65, 42 };，那么最大值就是65.（代码17-21行就是在查找最大值）

2、然后创建一个计数数组，计数数组的长度就是我们的待排序数组长度+1。即65+1=66。计数数组的作用就是用来存储待排序数组中，数字出现的频次。 例如，4出现了两次，那么计数数组arrayCount[4]=2。 OK，现在应该明白为什么计数数组长度为什么是66而不是65了吧？ 因为为了存储0

    然后再创建一个存储返回结果的数组，数组长度与我们的原始数据长度是相同的。（24和26行）

3、进行计数（代码29至31行）

4、将计数数组进行数量累计，即arrayCount[i]+=arrayCount[i-1]（代码35行至代码37行）。　

　  目的是为了数据的稳定性， 这块我其实看了许久才看懂的…再次证明我的资质真的很差劲。 我来尽力解释一下：

     其实这个与后边那步结合着看理解起来应该更容易些。

     例如我们计数数组分别是 1 2 1 2 1 的话，那么就代表0出现了一次，1出现了两次，2出现了一次，3出现了两次。

　　这个是很容易理解的。 那我们再换个角度来看这个问题。

　　我们可以根据这个计数数组得到每个数字出现的索引位置，即数字0出现的位置是索引0，数字1出现的问题是索引1，2；数字2出现的位置是索引3，数字4出现的位置是索引4，5。。。。

　　OK，大家可以看到，这个索引位置是累加的，所以我们需要arrayCount[i]+=arrayCount[i-1]来存储每个数字的索引最大值。 这样为了后边的输出

5、最后，把原始数据从后往前输出；然后每个数字都能找到计数器的最后实现索引。  然后将数字存储在实际索引的结果数组中。 然后计数数组的索引--， 结果就出来了。

PS:计数排序其实是特别吃内存的

 

时间复杂度：

O(n+k)  

请对照下方代码：因为有n的循环，也有k的循环，所以时间复杂度是n+k

空间复杂度：

O(n+k)  

请对照下方代码：需要一个k+1长度的计数数组，需要一个n长度的结果数组，所以空间复杂度是n+k

  1.     public static void main(String[] args) {
  2.  
  3.         int[] arrayData = { 2, 3, 1, 5, 6, 7, 4, 65, 42 };
  4.  
  5.         int[] arrayResult = CountintSort(arrayData);
  6.  
  7.     }
  1. public static int[] CountintSort(int[] arrayData) {
  2.     int maxNum = 0;
  3.     // 取出最大值
  4.     for (int i : arrayData) {
  5.         if (i > maxNum) {
  6.             maxNum = i;
  7.         }
  8.     }
  9.  
  10.     // 计数数组
  11.     int[] arrayCount = new int[maxNum + 1];
  12.     // 结果数组
  13.     int[] arrayResult = new int[arrayData.length];
  14.  
  15.     // 开始计数
  16.     for (int i : arrayData) {
  17.         arrayCount[i]++;
  18.     }
  19.  
  20.     // 对于计数数组进行 i=i+(i-1)
  21.     // 目的是为了保证数据的稳定性
  22.     for (int i = 1; i < arrayCount.length; i++) {
  23.         arrayCount[i] = arrayCount[i] + arrayCount[i - 1];
  24.     }
  25.  
  26.     for (int i = arrayData.length - 1; i >= 0; i--) {
  27.         arrayResult[arrayCount[arrayData[i]] - 1] = arrayData[i];
  28.         arrayCount[arrayData[i]]--;
  29.     }
  30.  
  31.     return arrayResult;
  32.  
  33. }

 

算法分析

        主要思想：根据array数组元素的值进行排序，然后统计大于某元素的元素个数，最后就可以得到某元素的合适位置；比如：array[4] = 9；统计下小于array[4]的元素个数为：8；所以array[4] = 9 应该放在元素的第8个位置；

        主要步骤：

       1、根据array数组，把相应的元素值对应到tmpArray的位置上；

     2、然后根据tmpArray数组元素进行统计大于array数组各个元素的个数；

     3、最后根据上一步统计到的元素，为array元素找到合适的位置，暂时存放到tmp数组中；

 

        如下图所示：array 是待排序的数组；tmpArray 是相当于桶的概念； tmp 是临时数组，保存array排好序的数组；

        

        注意：计数排序对输入元素有严格要求，因为array元素值被用来当作tmpArray数组的下标，所以如果array的元素值为100的话，那么tmpArray数组就要申请101（包括0，也就是 mix - min + 1）。

 

 

时间复杂度

        时间复杂度可以很好的看出了就是：O( n )；

 

空间复杂度

        空间复杂度也可以很好的看出来：O( n )；

 

总结

        计数排序的时间复杂度和空间复杂度都是非常有效的，但是该算法对输入的元素有限制要求，所以并不是所有的排序都使用该算法；最好的是0～9之间的数值差不会很大的数据元素间比较；有人会说这个没多大用，但是在后面的基数排序中会看到，这可以算是基数排序中的一个基础；

 

 

 

 

基数排序(Radix Sort)

 

　　基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机上的贡献。它是这样实现的：将所有待比较正整数统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始进行基数为10的计数排序，一直到最高位计数排序完后，数列就变成一个有序序列（利用了计数排序的稳定性）。

        基数排序的时间复杂度是O(n * dn)，其中n是待排序元素个数，dn是数字位数。这个时间复杂度不一定优于O(n log n)，dn的大小取决于数字位的选择（比如比特位数），和待排序数据所属数据类型的全集的大小；dn决定了进行多少轮处理，而n是每轮处理的操作数目。

　　如果考虑和比较排序进行对照，基数排序的形式复杂度虽然不一定更小，但由于不进行比较，因此其基本操作的代价较小，而且如果适当的选择基数，dn一般不大于log n，所以基数排序一般要快过基于比较的排序，比如快速排序。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序并不是只能用于整数排序。

 

基数排序已经不再是一种常规的排序方式，它更多地像一种排序方法的应用，基数排序必须依赖于另外的排序方法。基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。

如果按照习惯思维，会先比较百位，百位大的数据大，百位相同的再比较十位，十位大的数据大；最后再比较个位。人得习惯思维是最高位优先方式。但一旦这样，当开始比较十位时，程序还需要判断它们的百位是否相同--这就认为地增加了难度，计算机通常会选择最低位优先法。

基数排序方法对任一子关键字排序时必须借助于另一种排序方法，而且这种排序方法必须是稳定的。对于多关键字拆分出来的子关键字，它们一定位于0-9这个可枚举的范围内，这个范围不大，因此用桶式排序效率非常好。对于多关键字排序来说，程序将待排数据拆分成多个子关键字后，对子关键字排序既可以使用桶式排序，也可以使用任何一种稳定的排序方法。

 

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

 

算法分析

 

     主要思想：

        基数排序的实现虽然有很多，但是基本思想就是把元素从个位排好序，然后再从十位排好序，，，，一直到元素中最大数的最高位排好序，那么整个元素就排好序了。

                比如：2，22，31，1221，90，85，105

        个位排序：90，31，1221，2，22，85，105

        十位排序：2，105，1221，22，31，85，90

        百位排序：2，22，31，85，90，105，1221

        千位排序：2，22，31，85，90，105，1221

         注意：每次排序都是在上次排序的基础上进行排序的，也就是说此次排序的位数上他们相对时，就不移动元素（即顺序参数上一个位数的排序顺序）

 

    主要步骤：

        1、把所有元素都分配到相应的桶中

       2、把所有桶中的元素都集合起来放回到数组中

       3、依次循环上面两步，循环次数为最大元素最高位数

 

    代码分析：

        参考下图

     1、竖  0～9：表示桶个数（每个位数上的数字都在0到9之间）；

     2、行 0～length：0 表示在某个桶内有多少个元素；

     3、比如：所有元素中个位为5的有两个元素，5 ， 95；那么在下图中存放，分别是：（5，0） = 2；（5，1） = 5；（5，2）= 95；

 

基数排序是基于计数排序的，所以看这个之前要先看一下计数排序对于理解基数排序是很有帮助的（发现计数和基数的音节几乎一致啊）。

所谓基数排序，其实就是分别对数字的个位，十位，百位，百位。。。。分别进行计数排序。

当然可以从个位往上进行计数排序，也可以从高位往个数计数排序，这里我们使用个位往上计数排序的方法。

 

先从与计数排序的区别说起吧，区别在于计数排序是直接对数字进行排序。而基数排序是分别对个位，十位，百位。。。进行排序的。

然后，每个位数中，都有0至9共10个数字（即个数时，其实就是10个数字做排序；十数时，其实也是对10个数字做排序），接着我们对每个数字中的数字进行计数排序（好绕口，意思就是说，当进行个数排序时，个位为1时，所以个位为1的数字进行计排，例如11，21，31，221，411等等）。

所以我们申请的是二维数组int[][] radixBucket = new int[10][length]; （代码27行）  第一维的10存储的就是我们每次都是对10个数分别进行计排。第二维存储的就是对应的要排序的数字啦  

同时，因为我们要保证数字的稳定性，当我们把低位的数字进行计排后，要把低位数字输出至原始数组中，然后再进行高位排序。

 

  1. public class RadixSort {
  2.     public static void main(String[] args) {
  3.         int[] arrayData = { 2, 3, 1, 5, 6, 7, 4, 65, 42 };
  4.         RadixSortMethod(arrayData, 100);
  5.         for (int integer : arrayData) {
  6.             System.out.print(integer);
  7.             System.out.print(" ");
  8.         }
  9.     }
  10.  
  11.     /*
  12.      * arrayData - 要排序的数据 height - 要排序的步长 如果100，则只排序个位十位
  13.      */
  14.     public static void RadixSortMethod(int[] arrayData, int height) {
  15.         int maxNum = 0; // 最大值，用于存储桶数据临时数组空间大小
  16.         for (int data : arrayData) {
  17.             if (data > maxNum) {
  18.                 maxNum = data;
  19.             }
  20.         }
  21.  
  22.         int step = 1;
  23.         int length = arrayData.length;
  24.         int[][] radixBucket = new int[10][length]; // 二维数组，排序的容器
  25.         int[] arrayTemp = new int[maxNum + 1]; // 这个是每个桶中的数字个数
  26.         int num;
  27.         int index = 0;
  28.         while (step < height) {
  29.             for (int data : arrayData) {
  30.                 // 当step=1时统计个数，这时取出个位的数字。
  31.                 // 当step=10时，统计十数，这时取出十位的数字
  32.                 num = data / step % 10;
  33.                 radixBucket[num][arrayTemp[num]] = data;
  34.                 arrayTemp[num]++;
  35.             }
  36.  
  37.             for (int i = 0; i < 10; i++) {
  38.                 if (arrayTemp.length > i && arrayTemp[i] != 0) {
  39.                     for (int j = 0; j < arrayTemp[i]; j++) {
  40.                         arrayData[index] = radixBucket[i][j];
  41.                         index++;
  42.                     }
  43.                     arrayTemp[i] = 0; // 将当前数字个数重置为0，用于下次的统计
  44.                 }
  45.             }
  46.  
  47.             step *= 10;
  48.             index = 0;
  49.         }
  50.     }
  51. }

 

时间复杂度：

假设步长是s,待排序数组长度是n,数字最大值是m

那么时间复杂度就是O(s(n+(10*m)))=O(s(m+n))

 

空间复杂度：

待排序数组长度是n,数字最大值是m。

那么空间复杂度就是O(10*n+(m+1))=O(m+n)

 

稳定性：是稳定的

 

应用场景：

针对最大值相对比较小的正整数。

 

时间复杂度

        该算法所花的时间基本是在把元素分配到桶里和把元素从桶里串起来；把元素分配到桶里：循环 length 次；

       把元素从桶里串起来：这个计算有点麻烦，看似两个循环，其实第二循环是根据桶里面的元素而定的，可以表示为：k×buckerCount；其中 k 表示某个桶中的元素个数，buckerCount  则表示存放元素的桶个数；

       有几种特殊情况：

       第一、所有的元素都存放在一个桶内：k = length，buckerCount = 1；

       第二、所有的元素平均分配到每个桶中：k = length/ bukerCount，buckerCount = 10；（这里已经固定了10个桶）

       所以平均情况下收集部分所花的时间为：length （也就是元素长度 n）

 

       综上所述：

       时间复杂度为：posCount * (length  + length) ；其中 posCount 为数组中最大元素的最高位数；简化下得：O( k*n ) ；其中k为常数，n为元素个数；

 

空间复杂度

        该算法的空间复杂度就是在分配元素时，使用的桶空间；所以空间复杂度为：O（10 × length）= O （length）

 

 

 

 

桶排序(Bucket Sort)

 

　　桶排序也叫箱排序。工作的原理是将数组元素映射到有限数量个桶里，利用计数排序可以定位桶的边界，每个桶再各自进行桶内排序（使用其它排序算法或以递归方式继续使用桶排序）。

桶排序可用于最大最小值相差较大的数据情况，比如[9012,19702,39867,68957,83556,102456]。
但桶排序要求数据的分布必须均匀，否则可能导致数据都集中到一个桶中。比如[104,150,123,132,20000], 这种数据会导致前4个数都集中到同一个桶中。导致桶排序失效。

桶排序的基本思想是：把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并。
计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。

1.找出待排序数组中的最大值max、最小值min
2.我们使用 动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1
3.遍历数组 arr，计算每个元素 arr[i] 放的桶
4.每个桶各自排序
5.遍历桶数组，把排序好的元素放进输出数组

 

桶排序的逻辑其实特别好理解，它是一种纯粹的分而治之的排序方法。

举个例子简单说一下大家就知道精髓了。

假如对11,4,2,13,22,24,20 进行排序。

那么，我们将4和2放在一起，将11,13放在一起，将22,24,20放在一起。  然后将这三部分分别排序（可以根据实现情况任意选择排序方式，我的代码中使用的是快排），将子数组排序后，再顺序输出就是最终排序结果了（大概应该明白了，我们是根据数字大小进行分组的，故而顺序输出即可）

  1. /*
  2.  * 桶排序
  3.  */
  4. public class BucketSort {
  5.     public static void main(String[] args) {
  6.         int[] arrayData = { 22, 33, 57, 55, 58, 77, 44, 65, 42 };
  7.         BucketSortMethod(arrayData, 10);
  8.         for (int integer : arrayData) {
  9.             System.out.print(integer);
  10.             System.out.print(" ");
  11.         }
  12.     }
  13.  
  14.     /*
  15.      * buckenCount - 桶的数量
  16.      */
  17.     public static void BucketSortMethod(int[] arrayData, int buckenCount) {
  18.         int[][] arrayBucket = new int[buckenCount][arrayData.length]; // 桶容器
  19.  
  20.         for (int i = 0; i < arrayBucket.length; i++) {
  21.             for (int j = 0; j < arrayBucket[i].length; j++) {
  22.                 arrayBucket[i][j] = -1;
  23.             }
  24.         }
  25.  
  26.         int[] arrayLength = new int[arrayData.length];
  27.         int num;
  28.  
  29.         // 将数据分桶
  30.         for (int i = 0; i < arrayData.length; i++) {
  31.             // 根据结果来确定是存在在哪个桶中
  32.             num = arrayData[i] / buckenCount;
  33.             num = 10 - num; // 这是为了降序
  34.  
  35.             // System.out.println(num);
  36.             arrayBucket[num][arrayLength[num]] = arrayData[i];
  37.             arrayLength[num]++;
  38.         }
  39.  
  40.         // 将桶内数据进行排序，这里使用的是快排
  41.         for (int i = 0; i < arrayBucket.length; i++) {
  42.             QuickSort.QuickSortMethod(arrayBucket[i]);
  43.         }
  44.  
  45.         int resultIndex = 0;
  46.         // 对于桶内的数据进行输出
  47.         for (int i = 0; i < arrayBucket.length - 1; i++) {
  48.             if (arrayLength[i] > 0) {
  49.                 for (int j = 0; j < arrayBucket[i].length; j++) {
  50.                     if (arrayBucket[i][j] != -1) {
  51.                         arrayData[resultIndex++] = arrayBucket[i][j];
  52.                     }
  53.                 }
  54.             }
  55.         }
  56.     }
  57. }

 

 

时间复杂度：

时间复杂度主要还是取决于子数组的排序时间复杂度。 子数组的排序复杂度平均是O(n*log2n)，然后分桶这块的的空间复杂度是O(n)

即O(n+n*log2n)

 

空间复杂度：

假设桶的数量是b，待排序数组的长度是n。

那么O(b*n)=O(n)

 

稳定性：稳定性主要取决于子数组中的排序（即44行调用的快排），子数组中使用的排序方法是稳定的，那么桶排序就是稳定的。

 

.

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/794994
推荐阅读
相关标签

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

  

闽ICP备14008679号