偶看新闻螳螂虾vs蓝环章鱼视频:【排序结构7】 基数排序
来源：百度文库 编辑：偶看新闻 时间：2024/05/07 08:21:56
《桶排序》中我们能够看到，数据值的范围越大，可能需要桶的个数也就越多，空间代价也就越高。对于上亿单位的关键字，桶排序是很不实用的。基数排序是对桶排序的一种改进，这种改进是让“桶排序”适合于更大的元素值集合的情况，而不是提高性能。
多关键字排序问题(类似于字典序)：
我们先看看扑克牌的例子。一张牌有两个关键字组成：花色(桃<心<梅<方)+面值(2<3<4<... (1) 首先按照花色对所有牌进行稳定排序，这样就可以将所有牌分成4组。然后同组的牌(同花色)再按照面值进行排序。 (2) 首先按照面值对所有牌进行稳定排序，然后按照花色再次对所有牌进行稳定排序。 显然，第一种方法需要将序列分割成几个子序列。而第二种方法则完全不需要。因此我们采用从次关键字排序开始的方法。 基数排序 上面的问题是多关键字的排序，但单关键字也仍然可以使用这种方式。 比如字符串“abcd” “aesc” "dwsc" "rews"就可以把每个字符看成一个关键字。另外还有整数 425、321、235、432也可以每个位上的数字为一个关键字。 基数排序的思想就是将待排数据中的每组关键字依次进行桶分配。比如下面的待排序列： 278、109、063、930、589、184、505、269、008、083 我们将每个数值的个位，十位，百位分成三个关键字： 278 -> k1(个位)=8 ，k2(十位)=7 ，k3=(百位)=2。 然后从最低位个位开始(从最次关键字开始)，对所有数据的k1关键字进行桶分配(因为，每个数字都是 0-9的，因此桶大小为10)，再依次输出桶中的数据得到下面的序列。 930、063、083、184、505、278、008、109、589、269 再对上面的序列接着进行针对k2的桶分配，输出序列为： 505、008、109、930、063、269、278、083、184、589 最后针对k3的桶分配，输出序列为： 008、063、083、109、184、269、278、505、589、930 性能分析 很明显，基数排序的性能比桶排序要略差。每一次关键字的桶分配都需要O(N)的时间复杂度，而且分配之后得到新的关键字序列又需要O(N)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2N)，当然d要远远小于N，因此基本上还是线性级别的。基数排序的空间复杂度为O(N+M)，其中M为桶的数量。一般来说N>>M，因此额外空间需要大概N个左右。 但是，对比桶排序，基数排序每次需要的桶的数量并不多。而且基数排序几乎不需要任何“比较”操作，而桶排序在桶相对较少的情况下，桶内多个数据必须进行基于比较操作的排序。因此，在实际应用中，基数排序的应用范围更加广泛。