图解"数据结构--内部排序算法"----分配排序：箱排序、基数排序

矫情吗；* 2022-05-18 03:49 214阅读 0赞

# **一、分配排序的基本思想** #

排序过程无须比较关键字，而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶：O(n)。

# **二、分配排序分类** #

本文介绍两种分配排序：箱排序、基数排序。

> ## **2.1 ****箱排序** ##

> ### 2.1.1 箱排序的基本思想 ###

>     假设有一组长度为N的待排关键字序列K\[1....n\]。首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数 ，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) ，那么该关键字k就作为B\[i\]中的元素(每个桶B\[i\]都是一组大小为N/M的序列)。接着对每个桶B\[i\]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B\[0\]....B\[M\]中的全部内容即是一个有序序列。

> ### **2.1.2\[桶—关键字\]映射函数** ###

>     bindex=f(key)   其中，bindex 为桶数组B的下标(即第bindex个桶), k为待排序列的关键字。桶排序之所以能够高效，其关键在于这个映射函数，它必须做到：如果关键字k1<k2，那么f(k1)<=f(k2)。也就是说B(i)中的最小数据都要大于B(i-1)中最大数据。很显然，映射函数的确定与数据本身的特点有很大的关系

> ###  **2.1.3 举例说明"桶排序的排序过程"** ###

> > **1.待排序列为整数形式**

> > 假如待排序列K= \{ 49、38 、35、 97 、 76、  73 、 27、 49 \}。这些数据全部在1—100之间。因此我们定制10个桶，然后确定映射函数f(k)=k/10。则第一个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆入桶中，并在每个非空的桶中进行快速排序后得到如下图所示：

![080dd8d8-c5e3-3b29-9743-8f7f8e9e9bad.gif][]

> > 对上图只要顺序输出每个B\[i\]中的数据就可以得到有序序列了。

**2.待排序列为小数形式**

> > 假如待排序列K= \{ 0.78，0.17，0.39，0.26，0.72，0.94，0.21， 0.12，0.23，0.68 \}。我们定制10个桶(R\[0..9\])，然后确定映射函数f(k)=k\*10。则第一个关键字0.78将定位到第7个桶中。依次将所有关键字全部堆入桶中，并在每个非空的桶中进行快速排序后得到如下图所示：

> ![1351648210_6569.jpg][]  
>

**桶排序过程分析：**

这里n=10，故B\[0..9\]这10个桶表示的子区间分别是\[0，0.1)，\[0.1，0.2)，…，\[0.9，1)。

收集过程只要按B\[0\]，B\[1\]，…，B\[9\]的次序将各非空桶首尾链接起来，或将其输出到R\[0..9)中即可。

> ### **2.1.4 桶排序代价分析** ###

> > 桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的f(k)值的计算，其作用就相当于快排中划分，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。

> > 桶排序的平均时间复杂度为线性的O(N+C)，其中C=N\*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。此外，桶排序是稳定的。

**具体桶排序过程，见《[桶排序动画实例][Link 1]》**

> ## **2.2 基数排序** ##

> ### **2.2.1 多关键字排序实例** ###

**多关键字排序问题(类似于字典序)：**

> > 我们先看看扑克牌的例子。一张牌有两个关键字组成：花色(桃<心<梅<方)+面值(2<3<4<...<A)。假如一张牌的大小首先被花色决定，同花色的牌有数字决定的话。我们就有两种算法来解决这个问题。
> 
> > (1) 首先按照花色对所有牌进行稳定排序，这样就可以将所有牌分成4组。然后同组的牌(同花色)再按照面值进行排序。
> 
> > (2) 首先按照面值对所有牌进行稳定排序，然后按照花色再次对所有牌进行稳定排序
> 
> > 显然，第一种方法需要将序列分割成几个子序列。而第二种方法则完全不需要。因此我们采用从次关键字排序开始的方法。

> ### **2.2.2 基数排序基本思想** ###

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

> > **基数排序分为两种LSD和MSD。**

> > **LSD(Leastsignificant digital)**：最低有效位优先，即从右向左开始排序。 
> 
> > **MSD(Mostsignificant digital)**：最高有效位优先，即从左往右开始排序。
> > 
> >   
> >

> ### **2.2.2 举例说明"基数排序的排序过程"** ###

> > 比如字符串“abcd” “aesc” "dwsc" "rews"就可以把每个字符看成**一个关键字**。另外还有整数 425、321、235、432也可以每个位上的数字为**一个关键字**。

> > **基数排序的思想就是将待排数据中的每组关键字依次进行桶分配**。比如待排序列(123,252,611,52)       
> 
> > **排序过程如图：**

> > ![1351648285_6373.png][]
> > 
> > **基数排序过程分析：**
> > 
> > 我们将每个数的个位，十位，百位分成三个关键字： 278 -> k1(个位)=8  ，k2(十位)=7 ，k3=(百位)=2。
> > 
> > 然后从最低位个位开始(从**最次关键字**开始)，对所有数据的k1关键字进行桶分配(因为，每个数字都是 0-9的，因此桶大小为10)，再依次输出桶中的数据得到下面的序列。
> > 
> >                       611,252，052，123
> > 
> > 再对上面的序列接着进行针对k2的桶分配，输出序列为：
> > 
> >                       611，123，252，052
> > 
> > 最后针对k3的桶分配，输出序列为：
> > 
> >                       052，123，252，611
> > 
> >   
> > 
> > 
> > **更多基数排序测试，见《[基数排序动画演示][Link 2]》**
> > 
> >   
> > 
> > 
> > **返回《[内部排序综述][Link 3]》**
> > 
> >   
> > 
> > 
> >   
> >

[080dd8d8-c5e3-3b29-9743-8f7f8e9e9bad.gif]: /images/20220518/f9a973e9514a458caec6d87087b8f88b.png
[1351648210_6569.jpg]: https://img-my.csdn.net/uploads/201210/31/1351648210_6569.jpg
[Link 1]: http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/tongpaixu.htm
[1351648285_6373.png]: https://img-my.csdn.net/uploads/201210/31/1351648285_6373.png
[Link 2]: http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/jishupaixu.htm
[Link 3]: http://blog.csdn.net/mazhaojuan/article/details/8133888