数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会科学
服装学
法律研究置换排序
这是非比较排序技术的一个示例。它用于项目数量和可能关键值范围大致相同的情况。
要执行此排序，我们需要创建一些洞。所需孔的数量由数字范围决定。在每个孔中，都插入项目。最后从孔中删除并存储到数组中以进行排序。
置换排序技术复杂性
- 时间复杂度：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++) {
//delete from linked lists and store to array
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 << "Enter elements:" << 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 Enter elements: 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
更新于： 2020 年 6 月 15 日
825 次浏览
广告