鸽眼排序

这是非比较排序技术的一个示例。在项目数和可能的键值范围大致相同的情况下使用。

为了执行这种排序，我们需要做一些漏洞。所需的孔数由数字范围决定。在每个孔中插入项目。最后从孔中删除并存储到数组中以进行排序。

鸽孔分选技术的复杂性

• 时间复杂度：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