用于鸽孔排序的C ++程序？
鸽眼排序是非比较排序技术的一个示例。在项目数和可能的键值范围大致相同的情况下使用。
为了执行这种排序，我们需要做一些漏洞。所需的孔数由数字范围决定。在每个孔中插入项目。最后从孔中删除并存储到数组中以进行排序。
Pigeonhole排序，也称为计数排序，是一种排序算法，适用于对元素数量(n)和可能的键值(N)数量大致相同的元素列表进行排序。[1]它需要O（n+N）时间。
Input: arr[]={7,4,2,6,3,1,5}
Output: 1 2 3 4 5 6 7说明
在数组中找到最小和最大元素。最小和最大元素分别为“最小”和“最大”。然后找到范围为“max-min-1”。
设置一个最初为空的数组，以容纳与范围相同大小的“鸽子洞”。
遍历数组的每个元素，然后将每个元素放入其鸽子洞中。元素arr[i]将放入索引为arr[i]-min的孔中。
循环将按顺序从鸽孔阵列开始，并将所有非空孔中的元素放回到原始阵列中。
示例
#include <iostream>
using namespace std;
#define MAX 7
void pigeonhole_sort(int, int, int *);
int main() {
int i, min, max;
int a[]={7,4,2,6,3,1,5};
min = a[0];
max = a[0];
for (i = 1; i < MAX; i++) {
if (a[i] < min) {
min = a[i];
}
if (a[i] > max) {
max = a[i];
}
}
pigeonhole_sort(min, max, a);
for (i = 0; i < MAX; i++) {
cout<< a[i]<<"\t";
}
}
void pigeonhole_sort(int mi, int ma, int * a) {
int size, count = 0, i;
int *current;
current = a;
size = ma - mi + 1;
int holes[size];
for (i = 0; i < size; i++) {
holes[i] = 0;
}
for (i = 0; i < size; i++, current++) {
holes[*current-mi] += 1;
}
for (count = 0, current = &a[0]; count < size; count++) {
while (holes[count]--> 0) {
*current++ = count + mi;
}
}
}输出结果
1 2 3 4 5 6 7