用于鸽孔排序的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