数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C#堆排序
堆排序是一种利用堆数据结构的排序算法。每次移除堆的根元素（即最大元素）并将其存储到数组中。用最右边的叶子元素替换它，然后重建堆。重复此过程，直到堆中没有剩余元素，数组也就被排序。
下面是一个演示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);
}`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("
Sorted Array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
更新于：2020年6月26日
2K+ 次浏览
广告