算法基础 -- 堆排序之C语言实现

C语言实现堆排序（Heap Sort）

1. 代码实现

下面是 C语言实现的堆排序接口，支持 通用数据类型排序，并采用 函数指针 进行 自定义比较，适用于 整数排序 或 结构体排序。

完整代码

大根堆

#include <stdio.h>
#include <stdlib.h>
#include <string.h>/* 比较函数指针，返回值 >0 表示 a > b，=0 表示相等，<0 表示 a < b */
typedef int (*compare_func)(const void *, const void *);/* 交换函数 */
static void swap(void *a, void *b, size_t size) {void *temp = malloc(size);if (temp) {memcpy(temp, a, size);memcpy(a, b, size);memcpy(b, temp, size);free(temp);}
}/* 调整堆，保持最大堆性质 */
static void heapify(void *base, size_t nmemb, size_t size, size_t root, compare_func cmp) {size_t largest = root;size_t left = 2 * root + 1;size_t right = 2 * root + 2;char *arr = (char *)base;if (left < nmemb && cmp(arr + left * size, arr + largest * size) > 0) {largest = left;}if (right < nmemb && cmp(arr + right * size, arr + largest * size) > 0) {largest = right;}if (largest != root) {swap(arr + root * size, arr + largest * size, size);heapify(base, nmemb, size, largest, cmp);}
}/* 建立最大堆 */
static void build_heap(void *base, size_t nmemb, size_t size, compare_func cmp) {for (ssize_t i = (nmemb / 2) - 1; i >= 0; i--) {heapify(base, nmemb, size, i, cmp);}
}/* 堆排序 */
void heap_sort(void *base, size_t nmemb, size_t size, compare_func cmp) {if (!base || nmemb < 2 || !cmp) return;build_heap(base, nmemb, size, cmp);char *arr = (char *)base;for (size_t i = nmemb - 1; i > 0; i--) {swap(arr, arr + i * size, size);heapify(base, i, size, 0, cmp);}
}/* 整数比较函数 */
int int_compare(const void *a, const void *b) {return (*(int *)a - *(int *)b);
}/* 测试代码 */
int main() {int arr[] = {12, 11, 13, 5, 6, 7};size_t n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: ");for (size_t i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");heap_sort(arr, n, sizeof(int), int_compare);printf("排序后数组: ");for (size_t i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

小根堆

#include <stdio.h>
#include <stdlib.h>
#include <string.h>/* 比较函数指针，返回值 >0 表示 a > b，=0 表示相等，<0 表示 a < b */
typedef int (*compare_func)(const void *, const void *);/* 交换函数 */
static void swap(void *a, void *b, size_t size) {void *temp = malloc(size);if (temp) {memcpy(temp, a, size);memcpy(a, b, size);memcpy(b, temp, size);free(temp);}
}/* 调整堆，保持小根堆性质 */
static void min_heapify(void *base, size_t nmemb, size_t size, size_t root, compare_func cmp) {size_t smallest = root;size_t left = 2 * root + 1;size_t right = 2 * root + 2;char *arr = (char *)base;if (left < nmemb && cmp(arr + left * size, arr + smallest * size) < 0) {smallest = left;}if (right < nmemb && cmp(arr + right * size, arr + smallest * size) < 0) {smallest = right;}if (smallest != root) {swap(arr + root * size, arr + smallest * size, size);min_heapify(base, nmemb, size, smallest, cmp);}
}/* 建立小根堆 */
static void build_min_heap(void *base, size_t nmemb, size_t size, compare_func cmp) {for (ssize_t i = (nmemb / 2) - 1; i >= 0; i--) {min_heapify(base, nmemb, size, i, cmp);}
}/* 小根堆排序 */
void min_heap_sort(void *base, size_t nmemb, size_t size, compare_func cmp) {if (!base || nmemb < 2 || !cmp) return;build_min_heap(base, nmemb, size, cmp);char *arr = (char *)base;for (size_t i = nmemb - 1; i > 0; i--) {swap(arr, arr + i * size, size);min_heapify(base, i, size, 0, cmp);}
}/* 整数比较函数（小根堆适用） */
int int_compare_min(const void *a, const void *b) {return (*(int *)a - *(int *)b);
}/* 测试代码 */
int main() {int arr[] = {12, 11, 13, 5, 6, 7};size_t n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: ");for (size_t i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");min_heap_sort(arr, n, sizeof(int), int_compare_min);printf("小根堆排序后数组: ");for (size_t i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}