堆排序 -- C#代码实现

2021-01-07 10:16发布

using System;


namespace _3_1_1堆排序_顺序存储

{

    class Program

    {

        static void Main(string[] args)

        {

            int[] data = { 50, 10, 90, 30, 70, 40, 80, 60, 20 };

            HeapSort(data);

            foreach (int item in data)

            {

                Console.Write(item+" ");

            }

            Console.WriteLine();


            Console.ReadKey();


        }


        public static void HeapSort(int[] data)

        {

            //遍历这个数的所有非叶结点,挨个吧所有的子树变成子大顶堆

            for (int i = data.Length/2; i>=1; i--)

            {

                HeapAjusr(i, data, data.Length);

            }


            //剩下的子结点之间的转化

            for (int i = data.Length; i > 1; i--)

            {

                //把编号1和编号i的位置进行交换

                //1 到 (i-1) 构造成大顶堆

                int temp = data[0];

                data[0] = data[i - 1];

                data[i - 1] = temp;


                HeapAjusr(1,data,i-1);

            }

        }


        /// <summary>

        /// 堆调整

        /// </summary>

        private static void HeapAjusr(int number ,int[] data ,int maxNumber)

        {

            int maxNodeNum = number;

            int tempI = number;

            while (true)

            {

                //把i结点的子树变成大顶堆

                int leftChildNum = tempI * 2;

                int rightChileNum = leftChildNum + 1;

                if (leftChildNum <= maxNumber && (data[leftChildNum - 1] > data[maxNodeNum - 1]))

                {

                    maxNodeNum = leftChildNum;

                }

                if (rightChileNum <= maxNumber && data[rightChileNum - 1] > data[maxNodeNum - 1])

                {

                    maxNodeNum = rightChileNum;

                }

                if (maxNodeNum != tempI)  //发现一个比i更大的子结点,交互和

                {

                    int t = data[tempI - 1];

                    data[tempI - 1] = data[maxNodeNum - 1];

                    data[maxNodeNum - 1] = t;

                    tempI = maxNodeNum;

                }

                else

                {

                    break;

                }

            }

        }

    }

}

排序后的结果: 




作者:Czhenya

链接:https://czhenya.blog.csdn.net/article/details/78907413

来源:CSDN
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。