C语言堆排序

 

堆排序（Heapsort）是一种在时间复杂度上达到了最优的基于比较的排序算法。堆排序算法是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

堆排序的基本思想是：

1. 首先将待排序的序列构造成一个大顶堆（或小顶堆）。
2. 此时，整个序列的最大值（或最小值）就是堆顶的根节点。
3. 将其与末尾元素进行交换，此时末尾就为最大值（或最小值）。
4. 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值（或次大值）。
5. 如此反复执行，便能得到一个有序序列了。

堆排序的时间复杂度是O(n log n)。

#include <stdio.h>  // 将以k为根的子树调整为最大堆  
void heapify(int arr[], int n, int k) {  int largest = k;  // 初始化根节点最大  int left = 2 * k + 1;  // 左子节点  int right = 2 * k + 2;  // 右子节点  // 如果左子节点比根节点大，则更新最大节点  if (left < n && arr[left] > arr[largest]) {  largest = left;  }  // 如果右子节点比最大节点大，则更新最大节点  if (right < n && arr[right] > arr[largest]) {  largest = right;  }  // 如果最大节点不是根节点，则交换根节点和最大节点，并继续调整子树  if (largest != k) {  int temp = arr[k];  arr[k] = arr[largest];  arr[largest] = temp;  heapify(arr, n, largest);  }  
}  // 堆排序函数  
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);  }  
}  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函数将以k为根的子树调整为最大堆，heapSort函数则先构建最大堆，然后从堆顶开始取出元素并重新调整堆，最终得到排序后的数组。