减治法 堆排序C语言

堆排序是一种基于完全二叉树的排序算法，它的基本思想是将待排序的序列构造成一个大根堆或小根堆，然后将堆顶元素与堆底元素交换，再将剩余的元素重新构造成一个堆，重复执行以上步骤直到整个序列有序。堆排序的时间复杂度为O(nlogn)。

减治法是一种算法设计技术，它的基本思想是将一个大问题分解成若干个小问题，通过解决这些小问题来解决整个大问题。在堆排序中，减治法的思想体现在将待排序序列分解成一个个子序列，对每个子序列进行排序，最终将所有子序列合并成一个有序序列。

以下是堆排序的C语言实现代码：

#include <stdio.h>

void SiftHeap(int r[], int k, int n){
    int i, j, temp;
    i = k;
    j = 2 * i + 1;
    while(j < n){
        if(j < n - 1 && r[j] < r[j + 1]) j++;
        if(r[i] > r[j]) break;
        else{
            temp = r[i];
            r[i] = r[j];
            r[j] = temp;
            i = j;
            j = 2 * i + 1;
        }
    }
}

void HeapSort(int r[], int n){
    int i, temp;
    for(i = (n - 1) / 2; i >= 0; i--){
        SiftHeap(r, i, n);
    }
    for(i = 1; i <= n - 1; i++){
        temp = r[0];
        r[0] = r[n - i];
        r[n - i] = temp;
        SiftHeap(r, 0, n - i);
    }
}

int main(){
    int r[100], n;
    printf("请输入数组的长度：");
    scanf("%d", &n);
    printf("请输入数组的元素：");
    for(int i = 0; i < n; i++){
        scanf("%d", &r[i]);
    }
    HeapSort(r, n);
    printf("排序以后的数组为：");
    for(int i = 0; i < n; i++){
        printf("%d ", r[i]);
    }
    return 0;
}