[数据结构]堆排序的C语言简单实现

阳光穿透心脏的1/2处 2022-06-04 09:25 198阅读 0赞

今天突然要用到堆排序，所以按照算法导论的伪代码简单实现了一下。  
代码写得很简洁，例子也是用算法导论的例子，分别实现了小根堆，大根堆的代码，可以从小到大排序，也可以从大到小排序

#include <stdio.h>
    
    void MIN_HEAPIFY(int A[], int i, int n);
    void MAX_HEAPIFY(int A[], int i, int n);
    void BUILD_MIN_HEAR(int A[], int n);
    void BUILD_MAX_HEAR(int A[], int n);
    void swap(int *a, int *b);
    
    int main()
    {
        int N = 10, i;
        int A[] = {-1, 16, 14, 10, 8, 7, 9, 3, 2, 4, 1};
        for (i = 1; i <= N; ++i){
            printf("%d ", A[i]);
        }
        printf("\n");
        /*
        //从小到大排序
        BUILD_MIN_HEAR(A, N);
        for (i = 1; i <= N; ++i){
            printf("%d ", A[i]);
        }
        printf("\n");
        while (N >= 1){
            printf("%d ", A[1]);
            A[1] = A[N];
            N--;
            BUILD_MIN_HEAR(A, N);
        }
        */
        //从大到小排序
        BUILD_MAX_HEAR(A, N);
        for (i = 1; i <= N; ++i){
            printf("%d ", A[i]);
        }
        printf("\n");
        while (N >= 1){
            printf("%d ", A[1]);
            A[1] = A[N];
            N--;
            BUILD_MAX_HEAR(A, N);
        }
        return 0;
    }
    
    void BUILD_MIN_HEAR(int A[], int n){
        int i;
        for (i = n / 2; i >= 1; --i){
            MIN_HEAPIFY(A, i, n);
        }
    }
    
    void BUILD_MAX_HEAR(int A[], int n){
        int i;
        for (i = n / 2; i >= 1; --i){
            MAX_HEAPIFY(A, i, n);
        }
    }
    
    void MIN_HEAPIFY(int A[], int i, int n){
        int l = i * 2;  //左孩子下标
        int r = i * 2 + 1;  //右孩子下标
        int min = i;
        if (l <= n && A[l] < A[i]){
            min = l;
        }
        if (r <= n && A[r] < A[min]){
            min = r;
        }
        if (min != i){
            swap(&A[i], &A[min]);
            MIN_HEAPIFY(A, min, n);
        }
    }
    
    void MAX_HEAPIFY(int A[], int i, int n){
        int l = i * 2;  //左孩子下标
        int r = i * 2 + 1;  //右孩子下标
        int large = i;
        if (l <= n && A[l] > A[i]){
            large = l;
        }
        if (r <= n && A[r] > A[large]){
            large = r;
        }
        if (large != i){
            swap(&A[i], &A[large]);
            MAX_HEAPIFY(A, large, n);   //递归，调整交换后的结点
        }
    }
    
    void swap(int *a, int *b){  //交换元素
        int temp = *b;
        *b = *a;
        *a = temp;
    }