用于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”中。现在，对信鸽数组进行迭代，并将元素从填充的孔放回到原始数组中。这样，将对数组的所有元素进行排序。