算法实现/排序/鸽巢排序

此页面上当前的所有示例似乎都是 计数排序 的实现，而不是鸽巢排序。鸽巢排序在对具有键的复杂数据结构进行排序时，会跟踪特定键上的所有元素（因为相等的元素仍然是不同的）；而计数排序只跟踪计数（仅适用于简单的值类型）。

C99

void pigeonhole_sort(int *low, int *high, int min, int max)
{
   /* used to keep track of the size of the list we're sorting */
   int count; 
   /* pointer into the list we're sorting */
   int *current; 
   /* size of range of values in the list (ie, number of pigeonholes we need)*/
   const int size = max - min + 1;  
   /* our array of pigeonholes */
   int holes[size];  
 
   /* make absolutely certain that the pigeonholes start out empty */
   for (int i = 0; i < size; ++i)
          holes[i] = 0;
 
   /* Populate the pigeonholes.  */
   for (current = low; current <= high; current++)
      holes[*current - min] += 1;
 
   /* Put the elements back into the array in order.  */
   for (current = low, count = 0; count < size; count++)
      while (holes[count]-- > 0)
         *current++ = count + min;
}

请注意，min 和 max 也可以在函数内轻松确定。

Java

public static void pigeonhole_sort(int[] a)
{
    // size of range of values in the list (ie, number of pigeonholes we need)
    int min = a[0], max = a[0];
    for (int x : a) {
        min = Math.min(x, min);
        max = Math.max(x, max);
    }
    final int size = max - min + 1;

    // our array of pigeonholes
    int[] holes = new int[size];

    // Populate the pigeonholes.
    for (int x : a)
        holes[x - min]++;

    // Put the elements back into the array in order.
    int i = 0;
    for (int count = 0; count < size; count++)
        while (holes[count]-- > 0)
            a[i++] = count + min;
}

PHP

function pigeon_sort($arr)
{
//search min and max
$min = $max = $arr[0];
foreach ($arr as $num)
{       if ($num < $min)
                $min = $num;
        if ($num > $max)
                $max = $num;
}

foreach ($arr as $num)
        $d[$num-$min]++;

for ($i = 0; $i <= $max - $min; $i++ )
        while ($d[$i + $min]-- > 0)$res[] = $i+$min;
return $res;
}

Python

def pigeonhole_sort(a):
    # size of range of values in the list (ie, number of pigeonholes we need)
    my_min = min(a)
    my_max = max(a)
    size = my_max - my_min + 1

    # our list of pigeonholes
    holes = [0] * size

    # Populate the pigeonholes.
    for x in a:
        assert type(x) is int, "integers only please"
        holes[x - my_min] += 1

    # Put the elements back into the array in order.
    i = 0
    for count in xrange(size):
        while holes[count] > 0:
            holes[count] -= 1
            a[i] = count + my_min
            i += 1