C语言实现更加通用的排序算法

2020-01-11 / Algorithm Hacker C

初学C语言的学生应该都写过排序算法吧。选择排序、插入排序还有快速排序。但是最初开始学的时候写的都是对一组整数(int)进行排序。而且排序规则也是写死在函数内部的。那么问题来了,如果给你这样一个需求:实现一个排序函数,要能够允许用户自定义排序规则,而且要能处理各种各样的数据类型。

介绍

以上描述就是本文所需要实现的排序需求。

首先 我们要知道,所有其他语言能够实现的功能在C语言里面都是可以实现的。

再者 C语言是非常底层的语言,需要更多的去理解内存结构。

什么是排序算法

排序算法(Sorting Algorithm)就是一种用来将一组数据按照特定排序方式(例如:从小到大)进行重新排列的一种算法。最常考虑的排序方式就是数值顺序以及字典顺序。

排序算法的输出需要满足以下两个要求:

  1. 输出的元素任意两个相邻的元素必须满足排序算法定义的排序方式规则。
  2. 所有输出的结果应与原数据组中的数据一样且各元素个数也一样。

选择排序

冒泡排序

插入排序

快速排序

自定义排序规则

任意数据类型的排序

总结

bool cmp(const double *data_left, const double *data_right) {
    return *data_left <= *data_right;
}
void select_sort(const void *data_start, const void *data_end, size_t item_size,
                 bool (*cmp_func)(const void *, const void *)) {
    void *left = data_start;
    while (left < data_end) {
        void *min_p = left;
        void *cur = min_p + item_size;
        while (cur < data_end) {
            if (!cmp_func(min_p, cur)) {
                min_p = cur;
            }
            cur += item_size;
        }
        void *tmp = malloc(item_size);
        memcpy(tmp, left, item_size);
        memcpy(left, min_p, item_size);
        memcpy(min_p, tmp, item_size);
        free(tmp);
        left = left + item_size;
    }
}
select_sort(a, a + 10, sizeof(double), cmp);

喵喵怪的小枪枪、biu~