algorithm
ピジョンホールソート
サーチ…
ピジョンホールの基本情報のソート
Pigeonhole Sortは要素の数(n)と可能なキー値(N)の数がほぼ同じ要素のリストをソートするのに適したソートアルゴリズムです。ここで、nは入力配列の要素数であり、 'Range'は配列可能な値の数であるO(n + Range)時間が必要です。
Pigeonholeの作業(擬似コード)Sort:
- 最小値と最大値を配列で検索します。最小値と最大値をそれぞれ「min」と「max」とします。また、 'max-min-1'として範囲を見つける。
- 最初に空の "pigeonholes"の配列を範囲と同じサイズに設定します。
- 配列の各要素にアクセスし、各要素をピジョンホールに配置します。要素input [i]はindex input [i] - minの穴に入れられます。
- ピジョンホール配列全体をループで順番に開始し、空でない穴の要素を元の配列に戻します。
ピジョンホールの並べ替えは、並べ替えの種類に似ているので、ピジョンホールの並べ替えとカウントの並べ替えを比較します。
ピジョンホールソートの例:
スペース補助: O(n)
時間複雑度: O(n + N)
C#の実装
public class PigeonholeSort
{
private static void SortPigeonhole(int[] input, int n)
{
int min = input[0], max = input[n];
for (int i = 1; i < n; i++)
{
if (input[i] < min) min = input[i];
if (input[i] > max) max = input[i];
}
int range = max - min + 1;
int[] holes = new int[range];
for (int i = 0; i < n; i++)
{
holes[input[i] - min] = input[i];
}
int index = 0;
for (int i = 0; i < range; i++)
{
foreach (var value in holes)
{
input[index++] = value;
}
}
}
public static int[] Main(int[] input)
{
SortPigeonhole(input, input.Length);
return input;
}
}
Modified text is an extract of the original Stack Overflow Documentation
ライセンスを受けた CC BY-SA 3.0
所属していない Stack Overflow