C# heap sort

C# Heap sorting

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;  
        }  
    }  
}

The idea of ​​heap sorting:

Using the feature that the top of the big top heap (small top heap) records the largest keyword (the smallest keyword), It makes it simple to select the largest record (smallest record) from disorder every time.

The basic idea is (big top heap):

1) Construct the initial sequence of keywords to be sorted (R1, R2....Rn) into a large top heap. This heap is Initial unordered area;

2) Exchange the top element R[1] with the last element R[n], and get a new unordered area (R1, R2,... .Rn-1) and the new ordered area (Rn), and satisfy R[1,2...n-1]

3) Due to the new after exchange R[1] on the top of the heap may violate the nature of the heap, so the current unordered area (R1, R2,...Rn-1) needs to be adjusted to a new heap, and then R[1] and the unordered area need to be adjusted again The last element is exchanged to obtain a new disordered area (R1, R2...Rn-2) and a new ordered area (Rn-1, Rn). This process is repeated until the number of elements in the ordered area is n-1, then the entire sorting process is completed.

The operation process is as follows:

1) Initialize the heap: Construct R[1..n] as a heap;

2) Convert the top element of the current unordered area to the heap R[1] exchanges with the last record in the range, and then adjusts the new unordered area to the new heap.

Therefore, for heap sorting, the two most important operations are to construct the initial heap and the adjustment heap. In fact, constructing the initial heap is actually the process of adjusting the heap, but constructing the initial heap is for all non-leaf nodes. Make adjustments.

The above is the content of C# heap sort. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!