C# 中的堆排序
csharpprogrammingserver side programming
堆排序是一种利用堆数据结构的排序算法。每次移除堆的根元素，即最大元素，并将其存储在数组中。用最右边的叶元素替换它，然后重新建立堆。一直这样做，直到堆中没有剩余元素，数组已排序。
下面给出了一个演示 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("
Sorted 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 循环删除堆的根元素，即最大元素。它被最右边的叶元素替换，然后再次调用 heapify() 以重新建立堆。这可以在以下代码片段中看到。
for (int i = n-1; i>=0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
The function heapify() creates a heap structure by arranging the elements as required. This process starts from the element at index i for this is considered the root element for the heapify() function. This can be seen in the following code snippet.
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("
Sorted Array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
