C语言——堆排序

堆排序的过程可分为三个步骤：

• 维持堆的性质（这里指最大堆）
• 构建最大堆 （采用自底向上构建）
• 排序（将根节点值与堆底最右交换，推大小减一，并检查堆性质，循环堆大小减一次）

实现如下：

#include<stdio.h>
#include<stdlib.h>

/***************************************************************
 * 堆排序
 * 1、数组建堆（最大堆）——包括堆性质的维护和最大对构建
 * 2、排序
 ***************************************************************/


/***************************************************************
 * 宏定义函数
 * function     : parent(int i) 找出父节点下标
 * function     : left(int i) 找出左子节点下标
 * function     : right(int i) 找出右子节点下标
 **************************************************************/
#define PARENT(i) ((i)/2)
#define LEFT(i) ((i)*2)
#define RIGHT(i) ((i)*2+1)

/**********************************************************
 * function     : print_array
 * description  : 打印一个数组
 * input        : int A[],int length, char *print_string
 * output       : N/A
 * return value : N/A
 * author       : HanyoungXue
 * date         : 2018-4-15
 ***********************************************************/

void print_array(int A[],int length,char *print_string){
    printf("%s\n", print_string);
    for (int i = 0; i < length ; ++i){
        printf("%d\t",A[i]);
    }
    printf("\n");
}

/***************************************************************
 * function     : swap
 * description  : 交换数组的两个数据
 * input        : int A[],int a,int b
 * output       : int A[]
 * return value : N/A
 * author       : HanyoungXue
 * date         : 2018-4-15
 ***************************************************************/
void swap(int A[], int a,int b){
    int temp = A[a];
    A[a] = A[b];
    A[b] = temp;
}



/**************************************************************
 * function     : max_heapify(维护最大对性质)
 * description  : 如何一个堆的根节点值小于子节点值，与该子节点交换，
                  并检查该子节点为根节点的子树是否满足最大堆性质。
 * input        : int A[], int i,int heap_size
 * output       : int A[]
 * return value : N/A
 * author       : HanyoungXue
 * date         : 2018-4-15
 **************************************************************/


void max_heapify(int A[],int i,int heap_size){
    int left = LEFT(i);
    int right = RIGHT(i);
    int largest = i;
    if (left<heap_size && A[left]>A[largest]){
        largest = left;
    }

    if (right < heap_size && A[right]>A[largest]){
        largest = right;
    }

    if (largest!=i){
        swap(A,i,largest);
        max_heapify(A,largest,heap_size);
    }
}

/************************************************************
 * function     : build_max_heap
 * description  : 构建最大堆
 * input        : int A[],int heap_size
 * output       : int A[]
 * return value : N/A
 * author       : HanyoungXue
 * date         : 2018-4-15
 ************************************************************/

void build_max_heap(int A[],int heap_size){

    for (int i = heap_size/2-1; i >=0   ; i--){
        max_heapify(A,i,heap_size);
    }
    print_array(A,heap_size,"after build_max_heap:");
}


/***********************************************************
 * function     : heap_sort
 * description  : 堆排序
 * input        : int A[], int heap_size
 * output       : int A[]
 * return value : N/A
 * author       : HanyoungXue
 * date         : 2018-4-15
 ***********************************************************/

void heap_sort(int A[],int length){

    int heap_size = length;
    build_max_heap(A,heap_size);

    for (int i = heap_size -1 ; i >0; i--){
        swap(A,i,0);
        heap_size-=1;
        max_heapify(A,0,heap_size);
    }

}


int main(int argc, char const *argv[])
{
    int length = 12;
    int A[] = {5,7,2,20,9,11,16,25,18,14,13,21};
    print_array(A,length,"before heap_sort:");
    heap_sort(A,length);
    print_array(A,length,"after heap_sort:");
    return 0;
}