分布排序（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)算法实现举例

C代码
void PigeonholeSort(int *array, int length)
{
    int b[256] = {0};
    int i,k,j = 0;
    for(i=0; i<length; i++)
        b[array[i]]++;
    for(i=0; i<256; i++)
        for(k=0; k<b[i]; k++)
            array[j++] = i;
}
其实作者觉得鸽巢排序(Pigeonhole sort)的原理跟哈希表的原理类似——根据关键字的key就可以得到关键字的存储位置。

§2 桶排序（Bucket Sort）

箱排序(Bin Sort)

桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是比较排序，不受到 O(n log n) 下限的影响。

1、箱排序的基本思想

　箱排序也称桶排序(Bucket Sort)，其基本思想是：设置若干个箱子，依次扫描待排序的记录R[0]，R[1]，…，R[n-1]，把关键字等于k的记录全都装入到第k个箱子里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。

【例】要将一副混洗的52张扑克牌按点数A<2<…<J<Q<K排序，需设置13个"箱子"，排序时依次将每张牌按点数放入相应的箱子里，然后依次将这些箱子首尾相接，就得到了按点数递增序排列的一副牌。

2、箱排序中，箱子的个数取决于关键字的取值范围。

　若R[0..n-1]中关键字的取值范围是0到m-1的整数，则必须设置m个箱子。因此箱排序要求关键字的类型是有限类型，否则可能要无限个箱子。

3、箱子的类型应设计成链表为宜

　一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的，故箱子的类型应设计成链表为宜。

4、为保证排序是稳定的，分配过程中装箱及收集过程中的连接必须按先进先出原则进行。

（1）实现方法一

　每个箱子设为一个链队列。当一记录装入某箱子时，应做人队操作将其插入该箱子尾部；而收集过程则是对箱子做出队操作，依次将出队的记录放到输出序列中。

（2）实现方法二

　若输入的待排序记录是以链表形式给出时，出队操作可简化为是将整个箱子链表链接到输出链表的尾部。这只需要修改输出链表的尾结点中的指针域，令其指向箱子链表的头，然后修改输出链表的尾指针，令其指向箱子链表的尾即可。

桶排序算法实现举例

Cpp代码
#include <iostream>
#include <list>

using namespace std;

struct Node
{
     double value;
     Node *next;
};
//桶排序主程序
void bucketSort(double* arr, int length)
{
     Node key[10];
     int number = 0;
     Node *p, *q;//插入节点临时变量
     int counter = 0;
     for(int i = 0; i < 10; i++)
     {
         key[i].value = 0;
         key[i].next = NULL;
     }

     for(int i = 0; i < length; i++)
     {
         Node *insert = new Node();
         insert->value = arr[i];
         insert->next = NULL;
         number = arr[i] * 10;
         if(key[number].next == NULL)
         {
             key[number].next = insert;
         }
         else
         {
             p = &key[number];
             q = key[number].next;
             while((q != NULL) && (q->value <= arr[i]))
             {
                 q = q->next;
                 p = p->next;
             }
             insert->next = q;
             p->next = insert;
         }
     }
     for(int i = 0; i < 10; i++)
     {
         p = key[i].next;
         if(p == NULL)
             continue;
         while(p != NULL)
         {
             arr[coun

补充：软件开发 , C++ ,