C语言堆排序

 

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

堆排序的基本思想是：

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

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

#include   
  
// 将以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函数则先构建最大堆，然后从堆顶开始取出元素并重新调整堆，最终得到排序后的数组。