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

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

null

算法的工作原理：

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

                     /* C program to implement Pigeonhole Sort */                   
                     #include <bits/stdc++.h>                   
                     using                               namespace                               std;                   
                             
                     /* Sorts the array using pigeonhole algorithm */                   
                     void                               pigeonholeSort(                               int                               arr[],                               int                               n)                   
                     {                   
                                         // Find minimum and maximum values in arr[]                   
                                         int                               min = arr[0], max = arr[0];                   
                                         for                               (                               int                               i = 1; i < n; i++) {                   
                                         if                               (arr[i] < min)                   
                                         min = arr[i];                   
                                         if                               (arr[i] > max)                   
                                         max = arr[i];                   
                                         }                   
                                         int                               range = max - min + 1;                               // Find range                   
                             
                                         // Create an array of vectors. Size of array                   
                                         // range. Each vector represents a hole that                   
                                         // is going to contain matching elements.                   
                                         vector<                               int                               > holes[range];                   
                             
                                         // Traverse through input array and put every                   
                                         // element in its respective hole                   
                                         for                               (                               int                               i = 0; i < n; i++)                   
                                         holes[arr[i] - min].push_back(arr[i]);                   
                             
                                         // Traverse through all holes one by one. For                   
                                         // every hole, take its elements and put in                   
                                         // array.                   
                                         int                               index = 0;                               // index in sorted array                   
                                         for                               (                               int                               i = 0; i < range; i++) {                   
                                         vector<                               int                               >::iterator it;                   
                                         for                               (it = holes[i].begin(); it != holes[i].end(); ++it)                   
                                         arr[index++] = *it;                   
                                         }                   
                     }                   
                             
                     // Driver program to test the above function                   
                     int                               main()                   
                     {                   
                                         int                               arr[] = { 8, 3, 2, 7, 4, 6, 8 };                   
                                         int                               n =                               sizeof                               (arr) /                               sizeof                               (arr[0]);                   
                             
                                         pigeonholeSort(arr, n);                   
                             
                                         printf                               (                               "Sorted order is : "                               );                   
                                         for                               (                               int                               i = 0; i < n; i++)                   
                                         printf                               (                               "%d "                               , arr[i]);                   
                             
                                         return                               0;                   
                     }                   

输出：

Sorted order is : 2 3 4 6 7 8 8

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

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

THE END

技术文章