鸽眼排序
这是非比较排序技术的一个示例。在项目数和可能的键值范围大致相同的情况下使用。
为了执行这种排序，我们需要做一些漏洞。所需的孔数由数字范围决定。在每个孔中插入项目。最后从孔中删除并存储到数组中以进行排序。
鸽孔分选技术的复杂性
时间复杂度：O（n+2^k）
空间复杂度：O（2^k）
输入输出
Input: The unsorted list: 802 630 20 745 52 300 612 932 78 187 Output: Data before Sorting: 802 630 20 745 52 300 612 932 78 187 Data after Sorting: 20 52 78 187 300 612 630 745 802 932
算法
pigeonHoleSort(array, size)
输入-数据数组，以及数组中的总数
输出-排序的数组
Begin
find max and min from the array list
holeRange := max – min +1
define holeRange number of Lists
for i := 0 to n-1 do
hole[array[i]-min].append(array[i])
done
count := 0
for j := 0 to holeRange-1 do
while hole[j] is not empty do
array[count] := get first node of hole[j] and delete it
count := count +1
done
done
End示例
#include<iostream>
#include<list>
#include<cmath>
using namespace std;
void getMaxMin(int *arr, int n, int &maximum, int &minimum) {
maximum = minimum = arr[0]; //initially max and min ar arr[0]
for(int i = 1; i<n; i++) {
if(arr[i] > maximum)
maximum = arr[i]; //get maximum data
if(arr[i] < minimum)
minimum = arr[i]; //get minimum data
}
}
void pegionHoleSort(int *arr, int n) {
int max, min;
getMaxMin(arr, n, max, min);
int holeRange = max - min +1;
list<int> hole[holeRange]; //create an array of holes
for(int i = 0; i<n; i++) {
hole[arr[i]-min].push_back(arr[i]);
}
int count = 0;
for(int j = 0; j<holeRange; j++) {
//从链表中删除并存储到数组
while(!hole[j].empty()) {
arr[count] = *(hole[j].begin());
hole[j].erase(hole[j].begin());
count++;
}
}
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; //create an array with given number of elements
cout << "输入元素：" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Data before Sorting: ";
display(arr, n);
pegionHoleSort(arr, n);
cout << "Data after Sorting: ";
display(arr, n);
}输出结果
Enter the number of elements: 10 输入元素： 802 630 20 745 52 300 612 932 78 187 Data before Sorting: 802 630 20 745 52 300 612 932 78 187 Data after Sorting: 20 52 78 187 300 612 630 745 802 932