C# ヒープソート

C# ヒープソート

using System;  
using System.Collections;  
namespace Sort  
{  
    public class HeapSorter  
    {  
        public static int[] Sort(int[] sortArray)  
        {  
            BuildMaxHeap(sortArray);  
            for (int i = (sortArray.Length - 1); i > 0; i--)  
            {  
                Swap(ref sortArray[0], ref sortArray[i]); // 将堆顶元素和无序区的最后一个元素交换  
                MaxHeapify(sortArray, 0, i); // 将新的无序区调整为堆，无序区在变小              
            }  
            return sortArray;  
        }  
        /// <summary>  
        /// 初始大根堆，自底向上地建堆  
        /// 完全二叉树的基本性质，最底层节点是 n/2，所以从 sortArray.Length / 2 开始  
        /// </summary>  
        private static void BuildMaxHeap(int[] sortArray)  
        {  
            for (int i = (sortArray.Length / 2) - 1; i >= 0; i--)  
            {  
                MaxHeapify(sortArray,i, sortArray.Length);  
            }  
        }  
        /// <summary>  
        /// 将指定的节点调整为堆  
        /// </summary>  
        /// <param name="i">需要调整的节点</param>  
        /// <param name="heapSize">堆的大小，也指数组中无序区的长度</param>  
        private static void MaxHeapify(int[] sortArray, int i, int heapSize)  
        {  
            int left = 2 * i + 1; // 左子节点  
            int right = 2 * i + 2; // 右子节点  
            int larger = i; // 临时变量，存放大的节点值  
            // 比较左子节点  
            if (left < heapSize && sortArray[left] > sortArray[larger])  
            {  
                larger = left;  
            }  
            // 比较右子节点  
            if (right < heapSize && sortArray[right] > sortArray[larger])  
            {  
                larger = right;  
            }  
            // 如有子节点大于自身就交换，使大的元素上移。  
            if (i != larger)  
            {  
                Swap(ref sortArray[i], ref sortArray[larger]);  
                MaxHeapify(sortArray, larger, heapSize);  
            }  
        }  
        //数组内元素互换  
        private static void Swap(ref int a, ref int b)  
        {  
            int t;  
            t = a;  
            a = b;  
            b = t;  
        }  
    }  
}

ヒープソートの考え方:

ビッグトップヒープ(スモールトップヒープ)の先頭に最大のキーワード(最小キーワード)が記録される特徴を利用して、最大のレコードが毎回無秩序から選択（最小限の記録）をシンプルにしました。

基本的な考え方は (ビッグトップヒープ) です:

1) ソートされるキーワードの最初のシーケンス (R1、R2...Rn) を、初期の順序付けされていない領域であるビッグトップヒープに構築します

2。 ) 先頭の要素 R[1] を最後の要素 R[n] と交換すると、新しい非順序領域 (R1、R2、...Rn-1) と新しい順序領域 (Rn) が得られます。 R[1,2...n-1]

3) 交換後の新しいヒープトップ R[1] はヒープのプロパティに違反する可能性があるため、次のことが必要です。現在の順序なし領域 (R1、R2、...Rn-1) を新しいヒープに調整し、R[1] を再び順序なし領域の最後の要素と交換して、新しい順序なし領域 (R1) を取得します。 、R2 ...Rn-2) と新しい順序付けされた領域 (Rn-1,Rn)。この処理を順序付き領域の要素数が n-1 個になるまで繰り返し、ソート処理全体が完了します。

操作プロセスは次のとおりです:

1) ヒープを初期化します: R[1..n] をヒープとして構築します。

2) 現在の順序付けされていない領域の先頭要素 R[1] を最後のレコードと交換します。 range の値を変更し、新しい順序付けされていない領域を新しいヒープに調整します。

つまり、ヒープのソートで最も重要な 2 つの操作は、初期ヒープと調整ヒープの構築です。実際、初期ヒープの構築はヒープを調整するプロセスですが、初期ヒープの構築は、非ヒープをすべて調整することです。葉のノード。

上記は C# ヒープソートの内容です。さらに関連する内容については、PHP 中国語 Web サイト (www.php.cn) に注目してください。