免费 网站,wordpress 提请审批,百度搜索大数据,哪里下载中文版的wordpressC语言实现堆排序#xff08;Heap Sort#xff09;
1. 代码实现
下面是 C语言实现的堆排序接口#xff0c;支持 通用数据类型排序#xff0c;并采用 函数指针 进行 自定义比较#xff0c;适用于 整数排序 或 结构体排序。
完整代码
大根堆
#include stdio.h
#…C语言实现堆排序Heap Sort
1. 代码实现
下面是 C语言实现的堆排序接口支持 通用数据类型排序并采用 函数指针 进行 自定义比较适用于 整数排序 或 结构体排序。
完整代码
大根堆
#include stdio.h
#include stdlib.h
#include string.h/* 比较函数指针返回值 0 表示 a b0 表示相等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 b0 表示相等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;
}
