分享一份归并排序代码，欢迎测试改进
程序代码：
/**
*\file merge_sort.h
*\brief 归并排序
*\date 2017/04/12
*/
#ifndef __MERGE_SORT_H_2017_04_12__
#define __MERGE_SORT_H_2017_04_12__
#ifdef __cplusplus
extern "C"{
#endif
/**
*\brief 归并排序中 设置merge_array的初始值
*\param[in] len 待初始化的数据规模
*\param[in] disoder_ary 等待排序的数据
*\param[in] merge_ary 初始化的对象
*\retval 1 初始化成功
*\retval 0 初始化失败
*/
typedef int (*merge_set_fun)(unsigned int len, void *disoder_ary, void **merge_ary);
/**
*\brief 归并排序中 两个元素对比函数
*\param[in] cmp1 对比元素1
*\param[in] cmp2 对比元素2
*\retval 1 cmp1 > cmp2
*\retval 0 cmp1 = cmp2
*\retval -1 cmp1 < cmp2
*/
typedef int (*merge_cmp_fun)(void *cmp1, void *cmp2);
/**
*\brief 归并排序中 赋值操作
*\param[in] lopr 被赋值的 等号 左边的数
*\param[in] ropr 赋值的 等号 右边的数
*\retval 1 赋值成功
*\retval 0 赋值失败
*/
typedef int (*merge_agn_fun)(void **lopr, void *ropr);
/**
*\brief 归并排序中 获取排序结果
*\param[in] len 获取结果的数据规模
*\param[in,out] res_ary 等待排序的数据
*\param[in] merge_ary 归并排序后的结果
*\retval 1 获取结果成功
*\retval 0 获取结果失败
*/
typedef int (*merge_res_fun)(unsigned int len, void *res_ary, void **merge_ary);
/**
*\brief 初始化归并排序环境
*\param[in] len 待排序的规模
*\param[in] disorder_array 待排序的数组
*\param[in] f_set 设置merge_array初始值函数
*\param[in] f_cmp 排序过程中需要的比较函数
*\param[in] f_agn 赋值操作函数
*\retval 1 初始化成功
*\retval 0 初始化失败
*/
int merge_init(unsigned int len, void *disorder_array,
merge_set_fun f_set,
merge_cmp_fun f_cmp,
merge_agn_fun f_agn);
/**
*\brief 销毁
*/
void merge_destory(void);
/**
*\brief 归并排序
*\param[in] len 获取排序结果结果规模
*\param[in,out] res_array 获取排序结果
*\param[in] f_res 获取结果的回调
*/
void merge_sort(unsigned int len, void *res_array, merge_res_fun f_res);
#ifdef __cplusplus
}
#endif
#endif//__MERGE_SORT_H_2017_04_12__
程序代码：
/**
*\file merge_sort.cc
*\brief 归并排序
*\date 2017/04/10
*/
#include "merge_sort.h"
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
static void **s_merge_array = (void**)0; ///< 交换的变量
static void **s_merge_swap = (void**)0; ///< 临时交换区
static unsigned int merge_len = 0; ///< 待排序的规模
static merge_cmp_fun mcmp_fun = NULL; ///< 对比函数
static merge_agn_fun magn_fun = NULL; ///< 赋值函数
static merge_set_fun mset_fun = NULL; ///< 设置merge_array的初始值
/**
*\brief 初始化归并排序环境
*\param[in] len 待排序的规模
*\param[in] disorder_array 待排序的数组
*\param[in] f_set 设置merge_array初始值函数
*\param[in] f_cmp 排序过程中需要的比较函数
*\param[in] f_agn 赋值操作函数
*\retval 1 初始化成功
*\retval 0 初始化失败
*/
int merge_init(unsigned int len, void *disorder_array,
merge_set_fun f_set,
merge_cmp_fun f_cmp,
merge_agn_fun f_agn)
{
assert(len > 1);
assert((void**)0 != disorder_array);
assert(NULL != f_set);
assert(NULL != f_set);
assert(NULL != f_set);
s_merge_array = (void **) malloc (sizeof(void*) * len);
s_merge_swap = (void **) malloc (sizeof(void*) * len);
if ((void**)0 == s_merge_array || (void**)0 == s_merge_swap){
printf("malloc failed errno(%d)!\n", errno);
if (s_merge_array){
free(s_merge_array);
s_merge_array = (void**)0;
}
if (s_merge_swap){
free(s_merge_swap);
s_merge_swap = (void**)0;
}
return 0;
}
merge_len = len;
mset_fun = f_set;
mcmp_fun = f_cmp;
magn_fun = f_agn;
return mset_fun(len, disorder_array, s_merge_array);
}
/**
*\brief 执行 归并排序
*\param[in] beg 起始位置下标
*\param[in] end 结束位置下标
*/
static void __msort(unsigned int beg, unsigned int end)
{
unsigned int mid = 0;
unsigned int i = 0, j = 0, k = 0;
int ret = 0;
assert (end >= beg);
if (end - beg >= 1){
mid = (end - beg) / 2;
__msort(beg, beg + mid);
__msort(beg + mid + 1, end);
// 归并 [beg, beg + mid] 和 [beg + mid + 1, end] 两个有序单元
for (i = beg, j = beg + mid + 1, k = beg; i <= beg + mid && j <= end; ++k){
ret = mcmp_fun(s_merge_array[i], s_merge_array[j]);
if (-1 == ret){
magn_fun(&s_merge_swap[k], s_merge_array[i]);
++i;
}else{
magn_fun(&s_merge_swap[k], s_merge_array[j]);
++j;
}
}
while (i <= beg + mid){ // 将剩余的全部拷贝
magn_fun(&s_merge_swap[k], s_merge_array[i]);
++k;
++i;
}
while(j <= end){ // 将剩余的全部拷贝
magn_fun(&s_merge_swap[k], s_merge_array[j]);
++k;
++j;
}
memcpy(&s_merge_array[beg], &s_merge_swap[beg], (end - beg + 1) * sizeof(void*));
}else{
// end == beg 表示只有一个， 不处理
}
}
/**
*\brief 归并排序
*\param[in] len 获取排序结果结果规模
*\param[in,out] res_array 获取排序结果
*\param[in] f_res 获取结果的回调
*/
void merge_sort(unsigned int len, void *res_array, merge_res_fun f_res)
{
__msort(0, merge_len - 1);
if (len <= 0 || NULL == res_array || NULL == f_res){// 不期望返回结果
return;
}
len = len > merge_len ? merge_len : len; // 取小的
f_res(len, res_array, s_merge_array);
}
/**
*\brief 销毁
*/
void merge_destory(void)
{
if (s_merge_array){
free(s_merge_array);
s_merge_array = (void**)0;
}
if (s_merge_swap){
free(s_merge_swap);
s_merge_swap = (void**)0;
}
merge_len = 0;
mset_fun = NULL;
mcmp_fun = NULL;
magn_fun = NULL;
}
程序代码：
/**
*\file main.cc
*\brief 归并排序
*\date 2017/04/10
*/
#include "merge_sort.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <assert.h>
#include <errno.h>
static int s_len = 0; ///< 待排序的数列长度
static int s_ary[10000]; ///< 存放数列
/**
*\brief 根据输入 随机创建
*/
static void creat_ary(void)
{
int i = 0;
printf("输入随机生成数列的数量:");
scanf("%d", &s_len);
assert(s_len > 1 && s_len < 10000);
srand(time(0));
for (i = 0; i < s_len; ++i){
s_ary[i] = rand()%10000;
}
}
/**
*\brief 输出随机产生的数列
*/
static void print_ary(void)
{
int i = 0;
for (i = 0; i < s_len; ++i){
printf("%d ", s_ary[i]);
}
printf("\n");
}
/**
*\brief 归并排序中 设置merge_array的初始值
*\param[in] len 待初始化的数据规模
*\param[in] disoder_ary 等待排序的数据
*\param[in] merge_ary 初始化的对象
*\retval 1 初始化成功
*\retval 0 初始化失败
*/
int set_fun(unsigned int len, void *disoder_ary, void **merge_ary)
{
unsigned int i = 0;
int *ary1 = NULL, **ary2 = NULL;
assert((void**)0 != disoder_ary);
assert((void**)0 != merge_ary);
ary1 = (int *)disoder_ary;
ary2 = (int **)merge_ary;
for (i = 0; i < len; ++i){
ary2[i] = &ary1[i];
}
return 1;
}
/**
*\brief 归并排序中 两个元素对比函数
*\param[in] cmp1 对比元素1
*\param[in] cmp2 对比元素2
*\retval 1 cmp1 > cmp2
*\retval 0 cmp1 = cmp2
*\retval -1 cmp1 < cmp2
*/
int cmp_fun(void *cmp1, void *cmp2)
{
int *int_cmp1 = NULL;
int *int_cmp2 = NULL;
assert(NULL != cmp1);
assert(NULL != cmp2);
int_cmp1 = (int*)cmp1;
int_cmp2 = (int*)cmp2;
if (*int_cmp1 > *int_cmp2){
return 1;
}else if (*int_cmp1 == *int_cmp2){
return 0;
}
return -1;
}
/**
*\brief 归并排序中 赋值操作
*\param[in] lopr 被赋值的 等号 左边的数
*\param[in] ropr 赋值的 等号 右边的数
*\retval 1 赋值成功
*\retval 0 赋值失败
*/
int agn_fun(void **lopr, void *ropr)
{
int **int_lopr = NULL;
int *int_ropr = NULL;
assert((void**)0 != lopr);
assert(NULL != ropr);
int_lopr = (int **)lopr;
int_ropr = (int *)ropr;
*int_lopr = int_ropr;
return 1;
}
/**
*\brief 归并排序中 获取排序结果
*\param[in] len 获取结果的数据规模
*\param[in,out] res_ary 等待排序的数据
*\param[in] merge_ary 归并排序后的结果
*\retval 1 获取结果成功
*\retval 0 获取结果失败
*/
int get_res_fun(unsigned int len, void *res_ary, void **merge_ary)
{
int *buf = NULL, **ary = (int**)0, *res = NULL;
unsigned int i = 0;
assert(0 <= len);
assert(NULL != res_ary);
assert((void**)0 != merge_ary);
buf = (int*) malloc (len * sizeof(int));
if (NULL == buf){
printf("malloc failed, errno(%d)\n", errno);
return 0;
}
ary = (int **)merge_ary;
res = (int *)res_ary;
for (i = 0; i < len; ++i){
buf[i] = *ary[i]; // 取指针指向的内容
}
memcpy(res, buf, len * sizeof(int));
return 1;
}
int main(int argc, char **argv)
{
creat_ary();
print_ary();
merge_init(s_len, (void *)s_ary, set_fun, cmp_fun, agn_fun);
merge_sort(s_len, (void *)s_ary, get_res_fun);
merge_destory();
print_ary();
return 0;
}
[此贴子已经被作者于2017-4-21 01:11编辑过]
code.zip