鸽巢排序的 Java 程序
java 8server side programmingprogramming
顾名思义，鸽巢排序的原理是创建鸽巢，鸽巢的数量使用"max-min+1"计算，也就是数组元素的范围。迭代原始数组中的元素，并根据特定条件将其放入鸽巢中。
此外，所有元素放入鸽巢后，会按照放入鸽巢的顺序重新放入数组中。
示例
以下是 Java 中鸽巢排序的示例 −
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"的位置。现在，迭代鸽笼数组，并将填充的鸽笼中的元素放回原始数组。这样，数组的所有元素都已排序。
