鸽巢排序(Pigeonhole sort)

算法效率

算法分析

算法代码(算法伪代码(类似Python代码格式) C源码)

鸽巢排序(Pigeonhole sort)

鸽巢排序, 也被称作基数分类, 是一种时间复杂度为(Θ(n))且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法. 但它只有在差值(或者可被映射在差值)很小的范围内的数值排序的情况下实用.

当涉及到多个不相等的元素, 且将这些元素放在同一个"鸽巢"的时候, 算法的效率会有所降低.为了简便和保持鸽巢排序在适应不同的情况, 比如两个在同一个存储桶中结束的元素必然相等

我们一般很少使用鸽巢排序, 因为它很少可以在灵活性, 简便性, 尤是速度上超过其他排序算法. 事实上, 桶排序较鸽巢排序更加的实用.

鸽巢排序的一个比较有名的变形是tally sort, 它仅仅适用非常有限的题目, 这个算法因在Programming Pearls一书中作为解决一个非常规有限集问题方法的例子而著名.

显然, 快速排序可以当作只有两个(有些情况下是三个)"鸽巢"的鸽巢排序

算法效率

最坏时间复杂度： O(N+n)

最好时间复杂度：O(N+n)

平均时间复杂度： O(N+n)

最坏空间复杂度：O(N*n)

算法分析

1. 给定一个待排序数组，创建一个备用数组（鸽巢），并初始化元素为0，备用数组的索引即是待排序数组的值。

2.把待排序数组的值，放到“鸽巢”里（即用作备用数组的索引）。

3.把鸽巢里的值再依次送回待排序数组。

算法代码

算法伪代码(类似Python代码格式)

def pigeonhole_sort ( array a[n] ) :

array auxiliary[N] = {0}

var i ,k

var j = 0

for i = 0 -> n

auxiliary[ a[i] ] ++

for i = 0 -> N

for k = 0 ->auxiliary[i]

a[j++] = i

C源码

void pigeonhole_sort(int* array, int length)

{

int auxiliary[NUM] = {0};

int i, k,j = 0;

for(i = 0; i < length; ++i)

auxiliary[array[i]]++;

for(i = 0; i < NUM; ++i)

for(k = 0; k < auxiliary[i]; ++k)

array[j++] = i;

}