效果图(Demo)

一图抵千言。

A picture paints a thousand words.

堆排序(Heap Sort)

堆排序总是建立这样一个二叉树：其父结点总大于其子结点。

Step 1: The first step of heap sort is to build a binary tree in which the parent node's value is always greater than its children nodes' value.

首先建堆。

It's called building the heap.

每轮将根结点与最后一个结点互换，然后对剩余部分建堆。

Step 2: Ater that, we swap the root node and the last node that hasn't been swapped yet.

Step 3: build the heap again like in step 1.

Step 4: if not all nodes are swapped in Step 2, goto Step2. Otherwise goto step 5.

Step 5: the heap sort is finished.

1         private static void HeapSortAscending1
      
       (this IList
       
         arr) 2             where T : IComparable 3         { 4             for (int i = arr.Count / 2 - 1; i >= 0; i--) 5             { 6                 arr.HeapAdjustAscending1(i, arr.Count); 7             } 8             for (int i = arr.Count - 1; i > 0; i--) 9             {10                 T temp = arr[0];11                 arr[0] = arr[i];12                 arr[i] = temp;13                 arr.HeapAdjustAscending1(0, i);14             }15         }16         private static void HeapAdjustAscending1
        
         (this IList
         
           arr, int nonLeafNodeToBeAdjusted, int unRangedCount)17             where T:IComparable18         {19             int leftChild = nonLeafNodeToBeAdjusted * 2 + 1;20             int rightChild = nonLeafNodeToBeAdjusted * 2 + 2;21             int max = nonLeafNodeToBeAdjusted;22             if (nonLeafNodeToBeAdjusted < unRangedCount / 2) // 是非叶节点(None leaf node)23             {24                 if (leftChild < unRangedCount && arr[leftChild].CompareTo(arr[max]) > 0)25                 { max = leftChild; }26                 if (rightChild < unRangedCount && arr[rightChild].CompareTo(arr[max]) > 0)27                 { max = rightChild; }28                 if (max!=nonLeafNodeToBeAdjusted)29                 {30                     T temp = arr[max];31                     arr[max] = arr[nonLeafNodeToBeAdjusted];32                     arr[nonLeafNodeToBeAdjusted] = temp;33                     arr.HeapAdjustAscending1(max, unRangedCount);34                 }35             }36         }