编辑代码

using System;

public class HelloWorld
{
    public static void Main()
    {
        int[] arr = { 23, 44, 66, 76, 98, 11, 3, 9, 7 };
        Console.WriteLine("排序前的数组：");
        foreach (int item in arr)
        {
            Console.Write(item + ",");
        }
        Console.WriteLine();
        HeapSort(arr, arr.Length - 1);
        Console.WriteLine("排序后的数组：");
        foreach (int item in arr)
        {
            Console.Write(item + ",");
        }
    }

    static void MaxHeapify(int[] array, int n, int i)
    {
        int largest = i;
        int lson = i * 2 + 1;
        int rson = i * 2 + 2;
        if (lson <= n && array[largest] < array[lson])
        {
            largest = lson;
        }
        if (rson <= n && array[largest] < array[rson])
        {
            largest = rson;
        }
        if (largest != i)
        {
            Swap(ref array[largest], ref array[i]);
            //递归调用
            MaxHeapify(array, n, largest);
        }
    }


    static void HeapSort(int[] array, int n)
    {
        //创建最大堆
        for (int i = n / 2 - 1; i >= 0; i--)
        {
            MaxHeapify(array, n, i);
        }
        //堆排序
        for (int i = n; i > 0; i--)
        {
            // 将最大值与最后一位交换，确定位置。
            Swap(ref array[i], ref array[0]);
            MaxHeapify(array, i - 1, 0);
        }
    }

    static void Swap(ref int a, ref int b)
    {
        int temp = b;
        b = a;
        a = temp;
    }
}