用于Pigeonhole排序的Java程序
顾名思义，将创建鸽子孔，其中使用“max-min+1”（也称为数组元素的范围）计算创建的鸽子孔的数量。根据特定条件，将原始数组中的元素进行迭代并放置在鸽子洞中。
此外，在将所有元素放入信鸽洞后，将它们按照它们在信鸽洞中放置的相同顺序放回到数组中。
示例
以下是Java中Pigeonhole排序的示例-
import java.lang.*;
import java.util.*;
public class Demo {
public static void pigeonhole_sorting(int my_arr[], int n) {
int min_element = my_arr[0];
int max_element = my_arr[0];
int my_range, i, j, index;
for(int a=0; a<n; a++) {
if(my_arr[a] > max_element)
max_element = my_arr[a];
if(my_arr[a] < min_element)
min_element = my_arr[a];
}
my_range = max_element - min_element + 1;
int[] sorted_arr = new int[my_range];
Arrays.fill(sorted_arr, 0);
for(i = 0; i<n; i++)
sorted_arr[my_arr[i] - min_element]++;
index = 0;
for(j = 0; j<my_range; j++)
while(sorted_arr[j]-->0)
my_arr[index++]=j+min_element;
}
public static void main(String[] args) {
Demo my_instance = new Demo();
int[] my_arr = {45, 67, 1, 20, 99, 74, 78};
System.out.print("The array, after performing pigeonhole sorting is : ");
my_instance.pigeonhole_sorting(my_arr,my_arr.length);
for(int i=0 ; i<my_arr.length ; i++)
System.out.print(my_arr[i] + " ");
}
}输出结果
The array, after performing pigeonhole sorting is : 1 20 45 67 74 78 99
说明
鸽孔排序通常用于对元素列表进行排序，其中元素的数量及其关联的键值几乎相同。它的时间复杂度为O（n+range），其中“n”是数组中元素的数量，“range”是指数组中关联键值的数量。
首先，找到数组的最小值和最大值。这些分别分配给两个变量。通过计算“max-min+1”可以找到该范围。
设置了一个带有空鸽子洞的数组，该数组的大小与范围的大小相同。数组中的每个元素都被迭代，并且每个元素都放置在鸽子洞中。这意味着如果元素在原始孔中的原始数组arr[i]中，则放置在“arr[i]-min_val”中。现在，对信鸽数组进行迭代，并将元素从填充的孔放回到原始数组中。这样，将对数组的所有元素进行排序。