通用算法的编写

前面我们写过各种各样的算法，但是我们在编写这些代码的时候却都有一个缺点，不知道大家发现了没有？那就是这些算法中使用的数据结构都是简单的int数据。所以，如果排序的是int，那么用起来没有什么问题。关键就是万一是其他的数据类型，那我们应该怎么办呢？

在 C++ 中，有一种解决的方法，那就是类函数。就拿冒泡排序来说，我们完全可以这么写。

template <typename type>
void bubbleSort(type array[], int length) 
{
    if(NULL == array || 0 == length) {
        return;
    }
    
    for (int i = 0; i < length - 1; i++) {
        for (int j = 0; j < length - i - 1; j++) {
            if (array[j] > array[j+1]) {
                type temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
    
    return;
}

当然，如果是一个 class 需要调用上面的算法的话，它还需要定义type缺省构造函数、type拷贝够构造函数两个函数。

那么，在 C 语言里面有没有什么办法呢？其实也有，那就是 void* 这种方法。

// 通用类型-冒泡排序（Bubble Sort）
void bubbleSort(void* array[], int length, int (* compare)(void*, void*), void(* swap)(void*, void*)) {
    for (int outer = 0; outer < length - 1; outer++) {
        for (int inner = 0; inner < length - outer - 1; inner++) {
            if(compare(array[inner], array[inner + 1])) {
                swap(array[inner], array[inner + 1]);
            }
        }
    }
    return;
}

在具体应用的时候，只需要将 void* 转换成自己需要的那个数据指针了。比如说，如果是 int 排序的话，我们就需要添加下面这两个函数即可。

int compare(void* var1, void* var2) {
    int* p_var1 = (int*)var1;
    int* p_var2 = (int*)var2;
    
    return (*p_var1 > *p_var2) ? 1 : 0;
}

void swap(void* var1, void* var2) {
    int* p_var1 = (int*)var1;
    int* p_var2 = (int*)var2;
    
    int temp = *p_var1;
    *p_var1 = *p_var2;
    *p_var2 = temp;
}

函数调用如下所示，数据转换稍显麻烦。

// 输出数组内容
void print(int array[], int length) {
    for (int j = 0; j < length; j++) {
        printf(" %d ", array[j]);
    }
    printf("\n");
}

int main(int argc, const char * argv[]) {
    int array[8] = { 49, 38, 65, 97, 76, 13, 27, 49 };
    int *p_arrayp[8];
    for (int i =0; i < 8; i ++) {
        p_arrayp[i] = &array[i];
    }
    bubbleSort((void**)p_arrayp, 8, compare, swap);
    print(array,8);
    
    return 0;
}

总结：

1. 写通用函数之前需要写好特定类型的算法函数
2. 通用算法的关键就是怎么样把通用的内容和具体的数据类型比较分开来
3. C++ 和 C 语言在通用算法各有各的方法，建议大家多多使用，特别是一些经常使用的函数