分享一个思路极其朴素的排序算法实现。鸽巢排序（Pigeonhole Sort）是个思路极其朴素的算法：适用于元素数量和取值范围大致相同的场景。

基本思路

  1. 找到数组的最大值 max 和最小值 min，取值范围就是 range = max - min + 1
  2. 开一个大小为 range 的”鸽巢”数组，初始为空
  3. 遍历原数组，每个元素 arr[i] 放进下标为 arr[i] - min 的鸽巢里
  4. 顺序遍历所有鸽巢，把非空的元素依次放回原数组

时间复杂度 O(n + Range)，n 是元素个数，Range 是取值范围。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void pigeonholeSort(int arr[], int n)
{
    int min = arr[0];
    int max = arr[0];
    int range, i, j, index;

    for (int a = 0; a < n; a++)
    {
        if (arr[a] > max) max = arr[a];
        if (arr[a] < min) min = arr[a];
    }

    range = max - min + 1;
    int *phole = (int *)malloc(range * sizeof(int));
    for (i = 0; i < range; i++)
        phole[i] = 0;

    for (i = 0; i < n; i++)
        phole[arr[i] - min]++;      // 每个元素进自己的鸽巢

    index = 0;
    for (j = 0; j < range; j++)
        while (phole[j]-- > 0)
            arr[index++] = j + min; // 按顺序放回原数组
}

适用场景

鸽巢排序用途有限，因为它要求元素个数和取值范围大致接近。比如给 100 个人的考试分数排序（分数范围 0~100），它就是 O(n) 的神；但如果范围远远大于元素个数，空间开销就不划算了，这时候用桶排序——它的泛化版本——会更有效率。

理解了鸽巢排序，再看计数排序和桶排序就是水到渠成的事。