堆排序

堆排序相對冒泡這些要複雜一些，它需要先初始化堆。.net裡List的排序就混合使用了堆排序和另2種排序。

出于學習目的，代碼示範裡不使用數組結構，數組取索引比較深澀。而使用嵌套類來實作。

1.初始化堆

排序肯定是有升序和降序兩種，堆排序也一樣，分為大頂堆和小頂堆。初始化堆的目的就是變為大頂堆或者小頂堆

傳統的方法是取數組下标[n/2]向下取整，但直接取最後一個元素往前周遊也是可行的

下面用22,44,6,88,5幾個數作為示範

step1.預設的樹結構

step2.自頂向下，以22開始先比較44和6兩個子樹，比較方式可以先比較左子樹和右子樹，取最大的值再和父節點比較。

44和6先進行比較，44比較大。然後44再和22進行比較，發現比父節點大。然後執行交換

step3.然後比較22的兩個子樹，88比較大，執行交換

step4.由于内部執行了交換，再次進行周遊。發現88比44大，執行交換。

至此，初始化堆完成

2.執行排序

堆排序有一個有序區和無序區的概念，有序區同樣在堆中，但是不參與排序。隻有無序區參與排序，排序結果轉移到有序區。

直到無序區沒有之後，排序結束

step1.是初始化好的堆，沒有進行任何操作

step2.需要不斷的把第一個元素和最後一個元素進行交換，放入有序區，橙色的是有序區

step3.交換完成之後，再重複進行初始化堆，進行調整

step4.由于88是有序區的内容，是以隻和左子樹22比較後，進行交換。

step5.再次和第一個元素進行交換，加入到有序區。

堆排序完成

下面附上代碼：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Hont
{
    public class HeapSort
    {
        public class Node
        {
            /// <summary>
            /// 用了一下空對象模式，省去了判斷null
            /// </summary>
            public readonly static Node EMPTY_NODE;

            public Node LeftChild { get; set; }
            public Node RightChild { get; set; }
            public Node Parent { get; set; }
            public int Value { get; set; }
            public bool IsUsed { get; set; }


            static Node()
            {
                EMPTY_NODE = new Node() { Value = 0, IsUsed = true };
            }

            public Node()
            {
                LeftChild = EMPTY_NODE;
                RightChild = EMPTY_NODE;
            }

            public Node(Node parent)
                : this()
            {
                this.Parent = parent;
            }
        }

        /// <summary>
        /// 執行排序
        /// </summary>
        /// <param name="sourceArray">原始數組</param>
        /// <param name="maxOrMin">降序還是升序</param>
        /// <returns>排序後的數組</returns>
        public int[] Sort(int[] sourceArray, bool maxOrMin = true)
        {
            Func<int, int, bool> compare = null;
            if (maxOrMin)
                compare = (a, b) => a > b;
            else
                compare = (a, b) => a < b;

            var rootNode = BuildHeap(sourceArray.ToList());
            AdjustHeap(rootNode, compare);
            SortHeap(rootNode, compare);
            return OutputHeap(rootNode).ToArray();
        }

        /// <summary>
        /// 建構堆，因為沒有用數組去實作，需要額外建構
        /// </summary>
        Node BuildHeap(List<int> sourceList)
        {
            Node result = new Node();
            List<Node> nextDepthNodeList = new List<Node>();
            List<Node> tmpNextDepthNodeList = new List<Node>();

            BuildHeap(result, sourceList, nextDepthNodeList);

            for (int i = 0; i < nextDepthNodeList.Count; i++)
            {
                var item = nextDepthNodeList[i];
                if (!BuildHeap(item, sourceList, tmpNextDepthNodeList))
                {
                    break;
                }

                if (i - 1 == nextDepthNodeList.Count)
                {
                    nextDepthNodeList = tmpNextDepthNodeList;
                    tmpNextDepthNodeList.Clear();
                    i = 0;
                }
            }

            var lastNode = GetLastSortNode(result);
            result.Value = lastNode.Value;
            if(lastNode.Parent.LeftChild == lastNode)
            {
                lastNode.Parent.LeftChild = Node.EMPTY_NODE;
            }
            else
            {
                lastNode.Parent.RightChild = Node.EMPTY_NODE;
            }

            return result;
        }

        bool BuildHeap(Node currentNode, List<int> sourceList, List<Node> nextDepthNodeList)
        {
            if (sourceList.Count < 1) return false;

            var firstNode = sourceList[0];
            currentNode.LeftChild = new Node(currentNode) { Value = firstNode };
            nextDepthNodeList.Add(currentNode.LeftChild);
            sourceList.RemoveAt(0);

            if (sourceList.Count > 0)
            {
                var lastNode = sourceList[sourceList.Count - 1];
                currentNode.RightChild = new Node(currentNode) { Value = lastNode };
                nextDepthNodeList.Add(currentNode.RightChild);
                sourceList.RemoveAt(sourceList.Count - 1);
            }

            return true;
        }

        /// <summary>
        /// 調整堆，調整至大頂堆或小頂堆，依據第二個參數
        /// </summary>
        void AdjustHeap(Node heap, Func<int, int, bool> compare)
        {
            if (heap == Node.EMPTY_NODE) return;

            if (heap.LeftChild.IsUsed && heap.RightChild.IsUsed) return;

            var leftChild = heap.LeftChild;
            var rightChild = heap.RightChild;
            var leftChildValue = heap.LeftChild.Value;
            var rightChildValue = heap.RightChild.Value;

            if (leftChild.IsUsed) leftChildValue = compare(int.MinValue, int.MaxValue) ? int.MaxValue : int.MinValue;
            if (rightChild.IsUsed) rightChildValue = compare(int.MinValue, int.MaxValue) ? int.MaxValue : int.MinValue;

            var selectChild = compare(leftChildValue, rightChildValue) ? leftChild : rightChild;
            var flag = compare(selectChild.Value, heap.Value);
            if (flag)
            {
                var tmp = heap.Value;
                heap.Value = selectChild.Value;
                selectChild.Value = tmp;
            }

            AdjustHeap(heap.LeftChild, compare);
            AdjustHeap(heap.RightChild, compare);

            if (flag)
            {
                AdjustHeap(heap, compare);
            }
        }

        void SortHeap(Node root, Func<int, int, bool> compare)
        {
            while (!root.IsUsed)
            {
                var lastNode = GetLastSortNode(root);
                var tmpHeapValue = root.Value;
                root.Value = lastNode.Value;
                lastNode.Value = tmpHeapValue;

                lastNode.IsUsed = true;
                AdjustHeap(root, compare);
            }
        }

        /// <summary>
        /// 獲得最後可用的堆成員，如果是IsUsed說明是有序區就跳過，主要用于排序時，首尾成員交換
        /// </summary>
        Node GetLastSortNode(Node root)
        {
            Node result = root;
            while (true)
            {
                if (result.RightChild != Node.EMPTY_NODE && !result.RightChild.IsUsed)
                {
                    result = result.RightChild;
                }
                else if (result.LeftChild != Node.EMPTY_NODE && !result.LeftChild.IsUsed)
                {
                    result = result.LeftChild;
                }
                else
                {
                    break;
                }
            }

            return result;
        }

        /// <summary>
        /// 周遊節點
        /// </summary>
        void ForeachNode(Node root, Action<Node> foreachContent)
        {
            if (root != Node.EMPTY_NODE)
            {
                foreachContent(root);
            }

            if (root.LeftChild != Node.EMPTY_NODE)
            {
                ForeachNode(root.LeftChild, foreachContent);
            }

            if (root.RightChild != Node.EMPTY_NODE)
            {
                ForeachNode(root.RightChild, foreachContent);
            }
        }

        List<int> OutputHeap(Node root)
        {
            List<int> result = new List<int>();

            ForeachNode(root, m => m.IsUsed = false);

            while (!root.IsUsed)
            {
                var tmpNode = GetLastSortNode(root);
                result.Add(tmpNode.Value);
                tmpNode.IsUsed = true;
            }

            return result;
        }
    }
}      

Heap Sort

調用：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Hont;

namespace HeapSortPackage
{
    class Program
    {
        static void Main(string[] args)
        {
            HeapSort heapSort = new HeapSort();
            var result = heapSort.Sort(new int[] { 22, 44, 88, 5, 6 }, true);

            Console.WriteLine(string.Join(",", result));
            Console.Read();
        }
    }
}      

View Code