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]<=R[n];

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]에 대한 현재 정렬되지 않은 영역은 범위의 마지막 레코드와 교환된 다음 정렬되지 않은 새 영역을 새 힙으로 조정합니다.

따라서 힙 정렬에서 가장 중요한 두 가지 작업은 초기 힙을 구성하는 것과 조정 힙을 구성하는 것입니다. 실제로 초기 힙을 구성하는 것은 실제로 힙을 조정하는 과정이지만 초기 힙을 구성하는 것은 리프가 아닌 모든 노드에 대해 조정합니다.

위 내용은 C# 힙 정렬 내용입니다. 더 많은 관련 내용은 PHP 중국어 홈페이지(www.php.cn)를 참고해주세요!