C# を使用してヒープ ソート アルゴリズムを作成する方法

C# を使用してヒープ ソート アルゴリズムを作成する方法

ヒープ ソート (ヒープ ソート) は、完全なバイナリ ヒープに基づくソート アルゴリズムであり、その時間計算量はああ（んろぐん）。この記事では、C# を使用してヒープ ソート アルゴリズムを作成し、詳細なコード例を示します。

1. ヒープの構築

ヒープ ソート アルゴリズムでは、まず最大ヒープ (または最小ヒープ) を構築する必要があります。最大ヒープの特性は、親ノードの値がその子ノードの値以上であるのに対し、最小ヒープの場合はその逆です。

最大のヒープを構築するには、配列を使用してヒープを表現します。ヒープのノードは階層順に配置されます。ノード インデックス i が与えられると、次の方法でその親ノードと子ノードのインデックスを見つけることができます:

• 親ノード インデックス = (i - 1) / 2
• 左子ノード インデックス = 2 * i 1
• 右側の子ノードのインデックス = 2 * i 2

これらのインデックスを使用すると、ヒープ内を簡単に移動し、大きく (または小さく) 移動できます。要素はプッシュされます。ヒープの一番上まで。

次は、C# を使用して最大ヒープを実装するサンプル コードです:

public void BuildMaxHeap(int[] arr, int n, int i)
{
    int largest = i; // 初始化最大元素的索引
    int left = 2 * i + 1; // 左子节点索引
    int right = 2 * i + 2; // 右子节点索引

    // 如果左子节点比父节点大，更新最大元素的索引
    if (left < n && arr[left] > arr[largest])
    {
        largest = left;
    }

    // 如果右子节点比父节点大，更新最大元素的索引
    if (right < n && arr[right] > arr[largest])
    {
        largest = right;
    }

    // 如果最大元素的索引不是父节点的索引，交换父节点和最大元素
    if (largest != i)
    {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        // 递归地建立最大堆
        BuildMaxHeap(arr, n, largest);
    }
}

2. Heap sort

最大ヒープを構築した後、次を使用できます。 heap sort 配列をソートするアルゴリズム。ヒープソートの考え方は、最大の要素を配列の末尾に連続的に交換し、ソートする配列の範囲を減らすことです。具体的な手順は次のとおりです。

• 最大ヒープを構築します
• ヒープの先頭要素と最後の要素を交換します
• ヒープを再調整します
• ソートされた配列に要素が 1 つだけ残るまで、上記の手順を繰り返します。

#次は、C# を使用してヒープ ソートを実装するサンプル コードです。

public void HeapSort(int[] arr)
{
    int n = arr.Length;

    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        BuildMaxHeap(arr, n, i);
    }

    // 交换堆顶元素和末尾元素，并重建最大堆
    for (int i = n - 1; i > 0; i--)
    {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        BuildMaxHeap(arr, i, 0);
    }
}

テスト コード

For ヒープ ソート アルゴリズムが正しいことを検証するには、ランダムに生成された配列をソートし、チェックする結果を出力するテスト コードを作成します。以下は、C# で書かれたヒープ ソート テスト コードの例です。

int[] arr = { 12, 11, 13, 5, 6, 7 };
HeapSort(arr);

Console.WriteLine("排序后的数组：");
foreach (var element in arr)
{
    Console.Write(element + " ");
}

概要

上記の手順により、C# を使用してヒープ ソート アルゴリズムを正常に作成できました。詳細なコード例が提供されます。ヒープ ソートは、ほとんどの場合に優れたパフォーマンスを提供する効率的なソート アルゴリズムです。この記事がヒープ ソート アルゴリズムの理解と実装に役立つことを願っています。

以上がC# を使用してヒープ ソート アルゴリズムを作成する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。