分布排序（distribution sorts）算法大串讲
本文内容框架：
§1 鸽巢排序（Pigeonhole）
§2 桶排序（Bucket Sort）
§3 基数排序（Radix Sort）
§4 计数排序（Counting Sort）
§5 Proxmap Sort
§6 珠排序(Bead Sort）
§7 小结
本文介绍的排序算法是基于分配、收集的排序算法，分配排序的基本思想：排序过程无须比较关键字，而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶：O(n)。不受比较排序算法时间复杂度O(nlogn)的下限限制。
§1 鸽巢排序（Pigeonhole）
鸽巢排序(Pigeonhole sort)
鸽巢排序(Pigeonhole sort)，也被称作基数分类, 是一种时间复杂度为O(n)且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法。但它只有在差值(或者可被映射在差值)很小的范围内的数值排序的情况下实用，同时也要求元素个数(n)和成为索引的值(N)大小相当。
鸽巢排序(Pigeonhole sort)算法的时间复杂度都是O(N+n)，空间复杂度是O(N)。
鸽巢排序(Pigeonhole sort)算法的思想就是使用一个辅助数组，这个辅助数组的下标对应要排序数组的元素值即使用辅助数组的下标进行排序，辅助数组元素的值记录该下标元素值的在要排序数组中的个数。
鸽巢排序(Pigeonhole sort)算法步骤：
1.对于给定的一组要排序的数组，需要初始化一个空的辅助数组（“鸽巢”）,把初始数组中的每个值作为一个key(“鸽巢”)即辅助数组的索引即是待排序数组的值。
2.遍历初始数组，根据每个值放入辅助数组对应的“鸽巢”
3.顺序遍历辅助数组，把辅助数组“鸽巢”中不为空的数放回初始数组中
鸽巢排序(Pigeonhole sort)算法实现举例
<div class="dp-highlighter" style="font-family: Consolas, 'Courier New', Courier, mono, serif; background-color: #e7e5dc; width: 687.0499877929688px; overflow: auto; padding-top: 1px; margin: 18px 0px !important; color: #333333; line-height: 26px;"><div class="bar" style="padding-left: 45px;"><div class="tools" style="padding: 3px 8px 10px 10px; font-size: 9px; line-height: normal; font-family: Verdana, Geneva, Arial, Helvetica, sans-serif; color: silver; background-color: #f8f8f8; border-left-width: 3px; border-left-style: solid; border-left-color: #6ce26c;">C代码 http://dsqiu.iteye.com/images/icon_star.png
页:
[1]