首页 > 代码库 > 最小堆排序

最小堆排序

/// <summary>
    /// 最小堆排序,把所有的排序元素放在数组中。构成一个完全二叉树。
    /// </summary>
    public class MyHeapSort
    {
        /// <summary>
        /// 创建最小堆
        /// </summary>
        /// <param name="list"></param>
        /// <param name="low"></param>
        /// <param name="high"></param>
        public void CreateHeap(List<int> list,int low,int high)
        {
            int temp = 0;
            int k = 0;
            //从第一个非叶子节点开始,一直到到跟节点
            for (int i = list.Count / 2; i >= low;i-- )
            {
                k = i;
                int j = 2 * k + 1;//左子节点
                temp = list[k];
                while (j <= high)
                {
                    //找到左右节点中较小的节点
                    if (j<high&&j+1<high&&
                        list[j] > list[j + 1])
                    {
                        j++;
                    }
                    //父节点和较小的子节点比较,如果父节点大,则交换位置
                    if (temp > list[j])
                    {
                        list[k] = list[j];
                        k = j;
                        j = 2 * k + 1;//循环到下一级节点
                    }
                    else
                    {
                        j = high + 1;//跳出循环
                    }
                }
                list[k] = temp;//放置父节点
            }
        }

        public void HeapSort()
        {
            List<int> l = new List<int>();
            l.Add(30);
            l.Add(10);
            l.Add(5);
            l.Add(4);
            l.Add(9);
            l.Add(2);
            l.Add(6);
            CreateHeap(l, 0, 6);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < l.Count; i++)
            {
                sb.AppendFormat("{0},", l[i]);
            }
            MessageBox.Show(sb.ToString());
        }
        

最小堆排序