数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究鸽巢排序的 C++ 程序？
鸽巢排序是非比较排序技术的一个示例。它用于项目数和可能关键值范围近似相同的情况。
为了执行这种排序，我们需要创建一些洞。所需洞的数量由数字范围决定。将项目插入每个洞中。最后从洞中删除并存储到数组中以进行排序。
鸽巢排序，也称为计数排序，是一种排序算法，适用于对元素列表进行排序，其中元素数 (n) 和可能的关键值数 (N) 近似相同。[1] 它需要 O(n + N) 时间。
Input: arr[]={7,4,2,6,3,1,5}
Output: 1 2 3 4 5 6 7说明
找出数组中的最小和最大元素。最小和最大元素分别是“最小值”和“最大值”。然后将范围设为“最大值-最小值-1”。
最初设置一个与范围大小相同的空“鸽巢”数组。
遍历数组中的每个元素，然后将每个元素放入其鸽巢。元素 arr[i] 将放在索引 arr[i] – min 处的洞中。
循环将按顺序从鸽巢数组重新开始，并将非空洞中的所有元素放回原始数组。
示例
#include <iostream>
using namespace std;
#define MAX 7
void pigeonhole_sort(int, int, int *);
int main() {
int i, min, max;
int a[]={7,4,2,6,3,1,5};
min = a[0];
max = a[0];
for (i = 1; i < MAX; i++) {
if (a[i] < min) {
min = a[i];
}
if (a[i] > max) {
max = a[i];
}
}
pigeonhole_sort(min, max, a);
for (i = 0; i < MAX; i++) {
cout<< a[i]<<"\t";
}
}
void pigeonhole_sort(int mi, int ma, int * a) {
int size, count = 0, i;
int *current;
current = a;
size = ma - mi + 1;
int holes[size];
for (i = 0; i < size; i++) {
holes[i] = 0;
}
for (i = 0; i < size; i++, current++) {
holes[*current-mi] += 1;
}
for (count = 0, current = &a[0]; count < size; count++) {
while (holes[count]--> 0) {
*current++ = count + mi;
}
}
}输出
1 2 3 4 5 6 7
更新于： 2019 年 8 月 19 日
469 次浏览
广告