使用教材

《“笨办法” 学C语言（Learn C The Hard Way）》
https://www.jianshu.com/p/b0631208a794

附加任务

[习题18]回调函数：指向函数的指针 int (*POINTER_NAME) = (int a ,int b);
https://www.jianshu.com/p/a63b9575c86a
" 再写一个排序算法，并修改 test_sorting，让它可以接受任意排序函数以及排序函数的回调比较，用它来测试你的两个算法。"

• 附加任务说白了，就是想要可以用 test_sorting( ..., ... , 排序函数， 排序规则)，也就是可以在main里面直接自由指定想要测试的排序函数以及排序规则；

排序算法

• 插入排序，图片取自WIKI，会动的，很形象；

Insertion-sort-example-300px.gif
https://en.wikipedia.org/wiki/Insertion_sort

• 代码参考

https://algs4.cs.princeton.edu/21elementary/Insertion.java.html

调试运行

$ make ex18_a
clang -Wall -g    ex18_a.c   -o ex18_a
$ ./ex18_a 4 1 7 3 2 0 8
Bubble_sort:
0 1 2 3 7 4 8 
8 7 4 3 2 0 1 
8 2 3 7 4 0 1 
Insert_sort:
0 1 2 3 4 7 8 
8 7 4 3 2 1 0 
4 1 7 3 2 0 8 

代码说明

1、 新增类型

• typedef int*(*sort_cb)(int* numbers, int count, compare_cb cmp);

2、修改函数 void test_sorting

• void test_sorting(int *numbers, int count, compare_cb cmp, sort_cb sort) {}
• 增加了第四个参数sort_cb sort
• 函数内部调用排序函数时写 int *sorted = sort(numbers, count, cmp);
  等价于 int *sorted = bubble_sort(numbers, count, cmp);
  等价于 int *sorted = insert_sort(numbers, count, cmp);
  代码运行时，具体是bubble_sort还是insert_sort，视main函数里的调用语句而定；

3、新增函数 插入排序 int *insert_sort

• 与冒泡的实现相比，函数结构其实几乎一致；

4、主函数调用

    printf("Bubble_sort:\n");
    test_sorting(numbers, count, sorted_order , bubble_sort);
    test_sorting(numbers, count, reverse_order, bubble_sort);
    test_sorting(numbers, count, strange_order, bubble_sort);
    
    printf("Insert_sort:\n");
    test_sorting(numbers, count, sorted_order , insert_sort);
    test_sorting(numbers, count, reverse_order, insert_sort);
    test_sorting(numbers, count, strange_order, insert_sort);

• { 从小到大，从大到小，乱七八糟 } x { 冒泡，插入}，3 * 2 = 6种组合；

5、附加任务的意义

• 如果以后增加了新的排序算法，比如选择排序、快速排序、希尔排序，归并排序等等，只要函数的接口满足typedef int*(*sort_cb)(int* numbers, int count, compare_cb cmp);，也就是传入这三个指定类型的参数，再返回的是一个int型指针，那就不必再修改test_sorting，直接在main里面写用例进行测试即可；

完整源码

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>

/* Our old friend die from ex17. */
void die(const char *message)
{
    if(errno) {
        perror(message);
    } else {
        printf("ERROR: %s\n", message);
    }
    
    exit(1);
}

// a typedef creates a fake type, in this
// case for a funciton pointer
typedef int(*compare_cb)(int a, int b);
typedef int*(*sort_cb)(int* numbers, int count, compare_cb cmp);


/**
*   A classic bubble sort function that uses the 
*   compare_cb to do the sorting.
*/
int *bubble_sort(int *numbers, int count, compare_cb cmp)
{
    int temp = 0;
    int i = 0;
    int j = 0;
    int *target = malloc(count * sizeof(int));
    
    if(!target) 
        die("Memory error.");
    
    memcpy(target, numbers, count * sizeof(int));
    
    for(i = 0 ; i < count; i++) {
        for(j = i+1 ; j < count-1; j++) {
            if(cmp(target[i], target[j+1]) > 0) {
                temp = target[j+1];
                target[j+1] = target[i];
                target[i] = temp;
            }
        }
    }
    
    return target;
}


int *insert_sort(int *numbers, int count, compare_cb cmp)
{
    int temp = 0;
    int i = 0;
    int j = 0;
    int *target = malloc(count * sizeof(int));
    if(!target) 
        die("Memory error.");
    
    memcpy(target, numbers, count * sizeof(int));
    
    for(i = 1; i < count; i++) {
        for(j = i; j > 0; j--) {
            if(cmp(target[j], target[j-1]) < 0) {
                temp = target[j-1];
                target[j-1] = target[j];
                target[j] = temp;
            }
        }
    }
    
    return target;
}


int sorted_order(int a, int b)
{
    return a - b;
}

int reverse_order(int a, int b) 
{
    return b - a;
}

int strange_order(int a, int b) 
{
    if(a == 0 || b == 0) {
        return 0;
    } else {
        return a % b;
    }
}

/**
*   Used to test that we are sorting things correctly
*   by doing the sort and printing it out.
*/
void test_sorting(int *numbers, int count, compare_cb cmp, sort_cb sort) 
{
    int i = 0;
    int *sorted = sort(numbers, count, cmp);
    
    if(!sorted)
        die("Failed to sort as requested.");
    
    for(i = 0; i < count; i++) {
        printf("%d ", sorted[i]);
    }
    printf("\n");
    
    free(sorted);
}

int main(int argc, char *argv[])
{
    if(argc < 2) die("USAGE: ex18 4 3 1 5 6");
    
    int count = argc - 1;
    int i = 0;
    char **inputs = argv + 1;
    
    int *numbers = malloc(count * sizeof(int));
    if(!numbers) die("Memory error.");
    
    for(i = 0 ; i < count; i++) {
        numbers[i] = atoi(inputs[i]);
    }
    
    printf("Bubble_sort:\n");
    test_sorting(numbers, count, sorted_order , bubble_sort);
    test_sorting(numbers, count, reverse_order, bubble_sort);
    test_sorting(numbers, count, strange_order, bubble_sort);
    
    printf("Insert_sort:\n");
    test_sorting(numbers, count, sorted_order , insert_sort);
    test_sorting(numbers, count, reverse_order, insert_sort);
    test_sorting(numbers, count, strange_order, insert_sort);
    
    
    free(numbers);
    
    return 0;
}