堆在C#中排序

堆排序是一种利用堆数据结构的排序算法。每次堆的根元素（即最大的元素）被删除并存储在数组中。将其替换为最右边的leaf元素，然后重新建立堆。完成此操作，直到堆中不再有其他元素并且对数组进行排序为止。

给出了一个用C#演示堆排序的程序，如下所示。

示例

using System;
namespace HeapSortDemo {
   public class example {
      static void heapSort(int[] arr, int n) {
         for (int i = n / 2 - 1; i >= 0; i--)
         heapify(arr, n, i);
         for (int i = n-1; i>=0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
         }
      }
      static void heapify(int[] arr, int n, int i) {
         int largest = i;
         int left = 2*i + 1;
         int right = 2*i + 2;
         if (left < n && arr[left] > arr[largest])
         largest = left;
         if (right < n && arr[right] > arr[largest])
         largest = right;
         if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
         }
      }
      public static void Main() {
         int[] arr = {55, 25, 89, 34, 12, 19, 78, 95, 1, 100};
         int n = 10, i;
         Console.WriteLine("Heap Sort");
         Console.Write("Initial array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
         heapSort(arr, 10);
         Console.Write("\nSorted Array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
      }
   }
}

输出结果

上面程序的输出如下。

Heap Sort
Initial array is: 55 25 89 34 12 19 78 95 1 100
Sorted Array is: 1 12 19 25 34 55 78 89 95 100

现在，让我们了解以上程序。

该函数main()包含数组arr。它打印初始数组，然后调用heapSort()将对数组进行排序的函数。在下面的代码片段中可以看到。

int[] arr = {55, 25, 89, 34, 12, 19, 78, 95, 1, 100};
int n = 10, i;
Console.WriteLine("Heap Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
   Console.Write(arr[i] + " ");
}
heapSort(arr, 10);

该函数heapSort()首先将给定的元素转换为堆。这是通过使用for循环并heapify()为堆的所有非叶元素调用函数来完成的。在下面的代码片段中可以看到。

for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

创建堆之后，将使用for循环删除堆的根元素，即最大的元素。将其替换为最右边的leaf元素，然后heapify()再次调用以重新建立堆。在下面的代码片段中可以看到。

for (int i = n-1; i>=0; i--) {
   int temp = arr[0];
   arr[0] = arr[i];
   arr[i] = temp;
   heapify(arr, i, 0);
}

该函数heapify()通过按需排列元素来创建堆结构。此过程从索引i处的元素开始，因为它被认为是heapify()函数的根元素。在下面的代码片段中可以看到。

int largest = i;
int left = 2*i + 1;
int right = 2*i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
   int swap = arr[i];
   arr[i] = arr[largest];
   arr[largest] = swap;
   heapify(arr, n, largest);
}

最后，排序后的数组将显示在main()函数中。在下面的代码片段中可以看到。

Console.Write("\nSorted Array is: ");
for (i = 0; i < n; i++) {
   Console.Write(arr[i] + " ");
}