資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究Java鴿巢排序程式
顧名思義，會建立鴿巢，建立的鴿巢數量使用“最大值-最小值+1”計算得出，這也稱為陣列元素的範圍。迭代原始陣列中的元素，並根據特定條件將其放入鴿巢中。
此外，在將所有元素放入鴿巢後，會按照它們放入鴿巢的順序將它們放回陣列中。
示例
以下是Java中鴿巢排序的示例：
import java.lang.*;
import java.util.*;
public class Demo {
public static void pigeonhole_sorting(int my_arr[], int n) {
int min_element = my_arr[0];
int max_element = my_arr[0];
int my_range, i, j, index;
for(int a=0; a<n; a++) {
if(my_arr[a] > max_element)
max_element = my_arr[a];
if(my_arr[a] < min_element)
min_element = my_arr[a];
}
my_range = max_element - min_element + 1;
int[] sorted_arr = new int[my_range];
Arrays.fill(sorted_arr, 0);
for(i = 0; i<n; i++)
sorted_arr[my_arr[i] - min_element]++;
index = 0;
for(j = 0; j<my_range; j++)
while(sorted_arr[j]-->0)
my_arr[index++]=j+min_element;
}
public static void main(String[] args) {
Demo my_instance = new Demo();
int[] my_arr = {45, 67, 1, 20, 99, 74, 78};
System.out.print("The array, after performing pigeonhole sorting is : ");
my_instance.pigeonhole_sorting(my_arr,my_arr.length);
for(int i=0 ; i<my_arr.length ; i++)
System.out.print(my_arr[i] + " ");
}
}輸出
The array, after performing pigeonhole sorting is : 1 20 45 67 74 78 99
解釋
鴿巢排序通常用於對元素列表進行排序，其中元素數量及其關聯的鍵值幾乎相同。其時間複雜度為O(n+範圍)，其中“n”是陣列中元素的數量，“範圍”指的是陣列中關聯鍵值的個數。
首先，找到陣列的最小值和最大值。這些分別分配給兩個變數。範圍透過計算“最大值-最小值+1”來找到。
設定一個包含空鴿巢的陣列，該陣列的大小與範圍相同。迭代陣列中的每個元素，並將每個元素放入鴿巢中。這意味著如果原始陣列中位置為arr[i]的元素，在鴿巢中，它位於“arr[i]-最小值”位置。現在，迭代鴿巢陣列並將元素從填充的鴿巢放回原始陣列。這樣，陣列的所有元素都將被排序。
更新於：2020年9月14日
351 次檢視
廣告