Easton of the blog Easton个人博客

    /// <summary>
    /// 堆排序类
    /// </summary>
    public class HeapSort
    {
        /// <summary>
        /// 获得父节点下标
        /// </summary>
        /// <param name="i"></param>
        /// <returns></returns>
        static int GetParentIndex(int i)
        {
            return (i >> 1) + 1;
        }
        /// <summary>
        /// 获取左子节点下标
        /// </summary>
        /// <param name="i"></param>
        /// <returns></returns>
        static int GetLeftIndex(int i)
        {
            return (i << 1) + 1;
        }
        /// <summary>
        /// 获取右子节点下标
        /// </summary>
        /// <param name="i"></param>
        /// <returns></returns>
        static int GetRightIndex(int i)
        {
            return (i << 1) + 2;
        }
        /// <summary>
        /// 交换
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        static void exchange(ref int a, ref int b)
        {
            int temp = a;
            a = b;
            b = temp;
        }
        /// <summary>
        /// 保持最大堆的特性
        /// </summary>
        /// <param name="a"></param>
        /// <param name="i"></param>
        /// <param name="HeapSize"></param>
        static void MaxHeapify(int[] a, int i, int HeapSize)
        {
            //获得左子树节点下标
            int l = GetLeftIndex(i);
            //获得子树节点下标
            int r = GetRightIndex(i);
            int largest = i;
            if (l < HeapSize && a[l] > a[largest])
                largest = l;
            if (r < HeapSize && a[r] > a[largest])
                largest = r;
            //如果i不为根节点，则递归
            if (largest != i)
            {
                exchange(ref a[i], ref a[largest]);
                MaxHeapify(a, largest, HeapSize);
            }
        }
        /// <summary>
        /// 构建大根堆
        /// </summary>
        /// <param name="a"></param>
        static void BuildMaxHeap(int[] a)
        {
            for (int i = (a.Length >> 1) - 1; i >= 0; i--)
            {
                MaxHeapify(a, i, a.Length);
            }
        }
        /// <summary>
        /// 堆排序
        /// </summary>
        /// <param name="a"></param>
        public static void Sort(int[] a)
        {
            //构建大根堆
            BuildMaxHeap(a);
            for (int i = a.Length - 1; i > 0; i--)
            {
                exchange(ref a[0], ref a[i]);
                MaxHeapify(a, 0, i);
            }
        }
    }