?

堆排序（Heapsort）是一種在時間復(fù)雜度上達到了最優(yōu)的基于比較的排序算法。堆排序算法是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆積是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子節(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點。

堆排序的基本思想是：

1. 首先將待排序的序列構(gòu)造成一個大頂堆（或小頂堆）。
2. 此時，整個序列的最大值（或最小值）就是堆頂?shù)母?jié)點。
3. 將其與末尾元素進行交換，此時末尾就為最大值（或最小值）。
4. 然后將剩余n-1個元素重新構(gòu)造成一個堆，這樣會得到n個元素的次小值（或次大值）。
5. 如此反復(fù)執(zhí)行，便能得到一個有序序列了。

堆排序的時間復(fù)雜度是O(n log n)。

#include <stdio.h>  // 將以k為根的子樹調(diào)整為最大堆  
void heapify(int arr[], int n, int k) {  int largest = k;  // 初始化根節(jié)點最大  int left = 2 * k + 1;  // 左子節(jié)點  int right = 2 * k + 2;  // 右子節(jié)點  // 如果左子節(jié)點比根節(jié)點大，則更新最大節(jié)點  if (left < n && arr[left] > arr[largest]) {  largest = left;  }  // 如果右子節(jié)點比最大節(jié)點大，則更新最大節(jié)點  if (right < n && arr[right] > arr[largest]) {  largest = right;  }  // 如果最大節(jié)點不是根節(jié)點，則交換根節(jié)點和最大節(jié)點，并繼續(xù)調(diào)整子樹  if (largest != k) {  int temp = arr[k];  arr[k] = arr[largest];  arr[largest] = temp;  heapify(arr, n, largest);  }  
}  // 堆排序函數(shù)  
void heapSort(int arr[], int n) {  // 構(gòu)建最大堆  for (int i = n / 2 - 1; i >= 0; i--) {  heapify(arr, n, i);  }  // 從堆頂開始取出元素，并重新調(diào)整堆  for (int i = n - 1; i >= 0; i--) {  int temp = arr[0];  arr[0] = arr[i];  arr[i] = temp;  heapify(arr, i, 0);  }  
}  int main() {  int arr[] = {10, 7, 8, 9, 1, 5};  int n = sizeof(arr) / sizeof(arr[0]);  printf("Original array: ");  for (int i = 0; i < n; i++) {  printf("%d ", arr[i]);  }  printf("\n");  heapSort(arr, n);  printf("Sorted array: ");  for (int i = 0; i < n; i++) {  printf("%d ", arr[i]);  }  printf("\n");  return 0;  
}

該代碼中，heapify函數(shù)將以k為根的子樹調(diào)整為最大堆，heapSort函數(shù)則先構(gòu)建最大堆，然后從堆頂開始取出元素并重新調(diào)整堆，最終得到排序后的數(shù)組。