資料結構
網路
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 次瀏覽
廣告