c# 实现堆排序

整体思路:利用堆的数据结构,每次都从中取出根节点,完成整体排序.

1堆的数据结构:

特点是,根是一棵完全二叉树,上边根节点的值要大于其左右子树所有节点,

其最重要的特征是:从根到叶的任一条路径都满足单调性,如果一颗完全二叉树满足这个特性,

那它也是一个堆.也正是依照这个特性,可将一颗形式上的完全二叉树调整成为堆,堆的重要操作有删除头结点,插入一个结点:

下面定义了一个最大堆

 1  public class MaxHeap
 2     {
 3         private List<int> m_nums { get; set; }
 4         //构造函数初始化内部数据,同时给出哨兵.
 5         public MaxHeap()
 6         {
 7             m_nums = new List<int>();
 8             m_nums.Add(int.MaxValue);
 9         }
10         //插入操作
11         public void Insert(int item)
12         {
13             //首先放到最后
14             int i = m_nums.Count();
15             m_nums.Add(item);
16             //跟父节点进行比较
17             for (; item>m_nums[i/2]; i/=2)
18             {
19                 //父节点下移
20                 m_nums[i] = m_nums[i / 2];
21             }
22             m_nums[i] = item;
23         }
24         //删除操作
25         public int Delete()
26         {
27             if (m_nums.Count <= 1)
28             {
29                 throw new Exception("heap is zero");
30             }
31             int result = m_nums[1];
32             //将最后的元素替换到根节点
33             m_nums[1] = m_nums.Last();
34             m_nums.RemoveAt(m_nums.Count()-1);
35             //从根节点开始,依次与左右孩子作比较,将较大者浮上来
36             int i = 1;
37             while (true)
38             {
39                 //判断返回条件
40                 if (IsBiggerThanChild(ref i))
41                     break;    
42             }
43             return result;
44         }
45 
46         private bool IsBiggerThanChild(ref int i)
47         {
48             //没有孩子的情况
49             if (2 * i >= m_nums.Count())
50             {
51                 return true;
52             }
53             //只有左孩子的情况
54             else if (2 * i + 1 >= m_nums.Count())
55             {
56                 if (m_nums[i] >= m_nums[2 * i])
57                     return true;
58                 else
59                 {
60                     var temp = m_nums[i];
61                     m_nums[i] = m_nums[2 * i];
62                     m_nums[2 * i ] = temp;
63                     i = 2 * i;
64                 }
65             }
66             //左右孩子都有的情况
67             else
68             {
69                 if (m_nums[i] >= Math.Max(m_nums[2 * i], m_nums[2 * i + 1]))
70                     return true;
71                 int bigChildIndex = (m_nums[2 * i] >= m_nums[2 * i + 1]) ? 2 * i : 2 * i + 1;
72                 var temp = m_nums[i];
73                 m_nums[i] = m_nums[bigChildIndex];
74                 m_nums[bigChildIndex] = temp;
75                 i = bigChildIndex;
76             }
77             return false;
78         }
79     }

有了 堆这个强大的数据结构,排序就很简单了

  public static void Heap_Sort(int[] nums)
        {
            int length = nums.Length;
            MaxHeap maxHeap = new MaxHeap();
            for (int i = 0; i < length; i++)
            {
                maxHeap.Insert(nums[i]);
            }
            for (int i = 0; i < length; i++)
            {
                nums[length - 1 - i] = maxHeap.Delete();
            }
        }