通用函数:
/* common.h */#ifndef _COMMON_H#define _COMMON_Hvoid swap(int *ap, int *bp);void print_array(const int array[], int n);#endif
/* common.c */#include "common.h"#includevoid swap(int *ap, int *bp){ int tmp; tmp = *ap; *ap = *bp; *bp = tmp;}void print_array(const int array[], int n){ int i; for(i = 0; i < n; i++) printf("%d ", array[i]); printf("\n");}
堆排序函数:
/* max_heap_sort.h */#ifndef _MAX_HEAP_SORT_H#define _MAX_HEAP_SORT_Hvoid perc_down(int array[], int i, int n);void heap_sort(int array[], int n);#endif
/* max_heap_sort.c */#include "max_heap_sort.h"#include "common.h"#define left_child(i) (2 * (i) + 1)void perc_down(int array[], int i, int n){ int child; int tmp; for(tmp = array[i]; left_child(i) < n; i = child) { child = left_child(i); if(child != n-1 && array[child + 1] > array[child]) child++; if(tmp < array[child]) array[i] = array[child]; else break; } array[i] = tmp;}void heap_sort(int array[], int n){ int i; for(i = n / 2; i >= 0; i--) /* 建立堆 */ perc_down(array, i, n); for(i = n-1; i > 0; i--) { swap(&array[0], &array[i]); /* 删除最大元素,其实是将当前最大堆的最大元素放到堆的末尾 */ perc_down(array, 0, i); }}
测试函数:
/* max_heap_sort_test.c */#include "max_heap_sort.h"#includeint main(void){ int array[] = { 31, 24, 45, 67, 54, 87, 98, 12, 15, 89}; heap_sort(array, 10); print_array(array);}
/* Makefile */target := testobjs := max_heap_sort_test.o max_heap_sort.o common.o$(target):$(objs) gcc -o $@ $^%.o:%.c gcc -c -o $@ $
测试结果: