学步园

// --------------------------------------------------------------------------------------------------------------------
// <copyright file="Program.cs" company="Chimomo's Company">
//
// Respect the work.
//
// </copyright>
// <summary>
//
// The heap sort.
//
// 堆排序是一种选择排序。时间复杂度为O(nlog2n)。
// 堆排序的特点是：在排序过程中，将排序数组看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中父节点和子节点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。
//
// 基本思想
// 1.将要排序的数组创建为一个大根堆。大根堆的堆顶元素就是这个堆中最大的元素。
// 2.将大根堆的堆顶元素和无序区最后一个元素交换，并将无序区最后一个位置列入有序区，然后将新的无序区调整为大根堆。
// 3.重复操作，直到无序区消失为止。
// 初始时，整个数组为无序区。每一次交换，都是将大根堆的堆顶元素插入有序区，以保证有序区是有序的。
//
// 完全二叉树的基本性质
// 数组中有n个元素，i是结点。1<=i<=n/2，也就是说数组的后一半元素都是叶子结点。
// i的父结点位置：i/2
// i的左子结点位置：i*2+1
// i的左子结点位置：i*2+2
//
// </summary>
// --------------------------------------------------------------------------------------------------------------------

namespace CSharpLearning
{
    using System;

    /// <summary>
    /// The program.
    /// </summary>
    public static class Program
    {
        /// <summary>
        /// The main.
        /// </summary>
        public static void Main()
        {
            int[] a = { 1, 4, 6, 2, 8, 7, 9, 3, 5, 10 };
            Console.WriteLine("Before Heap Sort:");
            foreach (int i in a)
            {
                Console.Write(i + " ");
            }

            Console.WriteLine("\r\n\r\nIn Heap Sort:");
            HeapSort(a);
            Console.WriteLine("\r\nAfter Heap Sort:");
            foreach (int i in a)
            {
                Console.Write(i + " ");
            }

            Console.WriteLine(string.Empty);
        }

        /// <summary>
        /// The heap sort.
        /// </summary>
        /// <param name="a">
        /// The a.
        /// </param>
        public static void HeapSort(int[] a)
        {
            BuildMaxHeap(a); // 建立大根堆。
            for (int i = a.Length - 1; i > 0; i--)
            {
                Swap(ref a[0], ref a[i]); // 将堆顶元素和无序区的最后一个元素交换。
                MaxHeaping(a, 0, i); // 将新的无序区调整为大根堆。

                // 打印数组。
                foreach (int k in a)
                {
                    Console.Write(k + " ");
                }

                Console.WriteLine(string.Empty);
            }
        }

        /// <summary>
        /// Build max heap.
        /// 初始化大根堆，由底向上建堆。
        /// 由完全二叉树的基本性质可知，最底层结点是从a.Length/2开始，所以从(a.Length/2)-1结点开始由底向上进行大根堆的调整。
        /// </summary>
        /// <param name="a">
        /// The a.
        /// </param>
        private static void BuildMaxHeap(int[] a)
        {
            for (int i = (a.Length / 2) - 1; i >= 0; i--)
            {
                MaxHeaping(a, i, a.Length);
            }
        }

        /// <summary>
        /// The max heaping.
        /// 将指定的结点调整为堆。
        /// </summary>
        /// <param name="a">
        /// The a.
        /// 待排序数组。
        /// </param>
        /// <param name="i">
        /// The i.
        /// 需要调整的结点。
        /// </param>
        /// <param name="heapSize">
        /// The heap Size.
        /// 堆的大小，也指数组中无序区的长度。
        /// </param>
        private static void MaxHeaping(int[] a, int i, int heapSize)
        {
            int left = 2 * i + 1; // 左子结点。
            int right = 2 * i + 2; // 右子结点。
            int large = i; // 临时变量，存放大的结点值。

            // 比较左子结点。
            if (left < heapSize && a[left] > a[large])
            {
                large = left;
            }

            // 比较右子结点。
            if (right < heapSize && a[right] > a[large])
            {
                large = right;
            }

            // 如有子结点大于自身就交换，使大的元素上移。
            if (i != large)
            {
                Swap(ref a[i], ref a[large]);
                MaxHeaping(a, large, heapSize);
            }
        }

        /// <summary>
        /// Swap values of the two integers.
        /// </summary>
        /// <param name="a">An integer a.</param>
        /// <param name="b">An integer b.</param>
        private static void Swap(ref int a, ref int b)
        {
            int tmp = a;
            a = b;
            b = tmp;
        }
    }
}

// Output:
/*
Before Heap Sort:
1 4 6 2 8 7 9 3 5 10

In Heap Sort:
9 8 7 5 4 1 6 3 2 10
8 5 7 3 4 1 6 2 9 10
7 5 6 3 4 1 2 8 9 10
6 5 2 3 4 1 7 8 9 10
5 4 2 3 1 6 7 8 9 10
4 3 2 1 5 6 7 8 9 10
3 1 2 4 5 6 7 8 9 10
2 1 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

After Heap Sort:
1 2 3 4 5 6 7 8 9 10
*/