数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究Java鸽巢排序程序
顾名思义，会创建鸽巢，创建的鸽巢数量使用“最大值-最小值+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+范围)，其中“n”是数组中元素的数量，“范围”指的是数组中关联键值的个数。
首先，找到数组的最小值和最大值。这些分别分配给两个变量。范围通过计算“最大值-最小值+1”来找到。
设置一个包含空鸽巢的数组，该数组的大小与范围相同。迭代数组中的每个元素，并将每个元素放入鸽巢中。这意味着如果原始数组中位置为arr[i]的元素，在鸽巢中，它位于“arr[i]-最小值”位置。现在，迭代鸽巢数组并将元素从填充的鸽巢放回原始数组。这样，数组的所有元素都将被排序。
更新于：2020年9月14日
351 次查看
广告