算法基础--堆排序之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; }