資料結構
網路
關係資料庫管理系統(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+ 次瀏覽
廣告