資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學使用堆排序演算法對10個元素的陣列進行排序的C++程式
堆排序基於二叉堆資料結構。在二叉堆中，對於最大堆，父節點的子節點小於或等於父節點；對於最小堆，父節點的子節點大於或等於父節點。
以下是一個解釋堆排序所有步驟的例子。
排序前包含10個元素的原始陣列為：
| 20 | 7 | 1 | 54 | 10 | 15 | 90 | 23 | 77 | 25 |
此陣列使用max-heapify構建成一個二叉最大堆。此最大堆表示為陣列，如下所示。
| 90 | 77 | 20 | 54 | 25 | 15 | 1 | 23 | 7 | 10 |
提取最大堆的根元素並將其放置在陣列的末尾。然後呼叫max-heapify將其餘元素轉換為最大堆。重複此操作，直到最終獲得排序後的陣列，如下所示：
| 1 | 7 | 10 | 15 | 20 | 23 | 25 | 54 | 77 | 90 |
使用堆排序演算法對10個元素的陣列進行排序的程式如下所示。
示例
#include<iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
int temp;
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
int temp;
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--) {
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
int main() {
int arr[] = { 20, 7, 1, 54, 10, 15, 90, 23, 77, 25};
int n = 10;
i nt i;
cout<<"Given array is: "<<endl;
for (i = 0; i *lt; n; i++)
cout<<arr[i]<<" ";
cout<<endl;
heapSort(arr, n);
printf("\nSorted array is: \n");
for (i = 0; i < n; ++i)
cout<<arr[i]<<" ";
}輸出
Given array is: 20 7 1 54 10 15 90 23 77 25 Sorted array is: 1 7 10 15 20 23 25 54 77 90
在上面的程式中，函式`heapify()`用於將元素轉換為堆。此函式是一個遞迴函式，它從其被呼叫的元素（在本例中為i）開始建立一個最大堆。演示此功能的程式碼片段如下所示：
void heapify(int arr[], int n, int i) {
int temp;
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}函式`heapSort()`使用堆排序對陣列元素進行排序。它從非葉子節點開始，並對每個節點呼叫`heapify()`。這將陣列轉換為二叉最大堆。如下所示：
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
此後，`heapSort()`函式在for迴圈的每次迭代中都獲取根元素，並將其放在陣列的末尾。然後呼叫`heapify()`以確保其餘元素仍然是一個最大堆。最終，所有元素都使用此方法從最大堆中取出，並得到一個排序後的陣列。如下所示：
for (int i = n - 1; i >= 0; i--) {
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}在`main()`函式中，首先顯示陣列。然後，呼叫`heapSort()`函式對陣列進行排序。如下面的程式碼片段所示：
cout<<"Given array is: "<<endl; for (i = 0; i < n; i++) cout<<arr[i]<<" "; cout<<endl; heapSort(arr, n);
最後，顯示排序後的陣列。如下所示：
printf("\nSorted array is: \n");
for (i = 0; i < n; ++i)
cout<<arr[i]<<" ";
更新於：2020年2月12日
2K+ 次瀏覽
廣告