鸽子洞排序的Java程序-yiteyi-C++库

鸽子洞分拣是一种排序算法，适用于对元素列表进行排序，其中元素的数量和可能的键值的数量大致相同。这需要( N + 范围 )时间，其中n是输入数组中的元素数，“Range”是数组中可能的值数。

null

算法的工作原理：

在数组中查找最小值和最大值。让最小值和最大值分别为“min”和“max”。也可以将范围设置为“最大-最小-1”。
设置一个初始为空的“鸽子洞”数组，其大小与范围的大小相同。
访问数组中的每个元素，然后将每个元素放入其鸽子洞。将一个元素arr[i]放置在孔中的索引arr[i]–min处。
按顺序在鸽子洞数组中开始循环，并将非空洞中的元素放回原始数组中。

                     /* Java program to implement Pigeonhole Sort */                   
                             
                     import                               java.lang.*;                   
                     import                               java.util.*;                   
                             
                     public                               class                               GFG {                   
                                         public                               static                               void                               pigeonhole_sort(                               int                               arr[],                   
                                         int                               n)                   
                                         {                   
                                         int                               min = arr[                               0                               ];                   
                                         int                               max = arr[                               0                               ];                   
                                         int                               range, i, j, index;                   
                             
                                         for                               (                               int                               a =                               0                               ; a < n; a++) {                   
                                         if                               (arr[a] > max)                   
                                         max = arr[a];                   
                                         if                               (arr[a] < min)                   
                                         min = arr[a];                   
                                         }                   
                             
                                         range = max - min +                               1                               ;                   
                                         int                               [] phole =                               new                               int                               [range];                   
                                         Arrays.fill(phole,                               0                               );                   
                             
                                         for                               (i =                               0                               ; i < n; i++)                   
                                         phole[arr[i] - min]++;                   
                             
                                         index =                               0                               ;                   
                             
                                         for                               (j =                               0                               ; j < range; j++)                   
                                         while                               (phole[j]-- >                               0                               )                   
                                         arr[index++] = j + min;                   
                                         }                   
                             
                                         public                               static                               void                               main(String[] args)                   
                                         {                   
                                         GFG sort =                               new                               GFG();                   
                                         int                               [] arr = {                               8                               ,                               3                               ,                               2                               ,                               7                               ,                               4                               ,                               6                               ,                               8                               };                   
                             
                                         System.out.print(                               "Sorted order is : "                               );                   
                             
                                         sort.pigeonhole_sort(arr, arr.length);                   
                             
                                         for                               (                               int                               i =                               0                               ; i < arr.length; i++)                   
                                         System.out.print(arr[i] +                               " "                               );                   
                                         }                   
                     }                   
                             
                     // Code contributed by Mohit Gupta_OMG <(0_o)>                   

输出：

Sorted order is : 2 3 4 6 7 8 8

请参阅完整的文章鸽子洞排序更多细节！

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章