ANSI C Mergesort
这是我在尝试重新进入C时编写的一个合并实现。
我对算法的最优性的反馈不太感兴趣(因为我可以读到无数篇文章)，但是对我的风格进行深入的批评将是非常感谢的。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void mergesort_recurse(int* in_array, int i, int j);
void merge(int* array, int left, int centre, int right);
void mergesort(int* in_array, int len) {
mergesort_recurse(in_array, 0, len);
}
void mergesort_recurse(int* in_array, int left, int right) {
int length = right-left;
/*Base case: There are only two elements - Compare them and swap if
necessary.*/
if(length == 2) {
if(in_array[left] > in_array[right-1]) {
int temp = in_array[right-1];
in_array[right-1] = in_array[left];
in_array[left] = temp;
}
}
/*Leaves of lenth 1 can be ignored as they are already "sorted"*/
else if(length > 1){
/*Split into two and sort recursively.*/
int centre = left + length / 2;
mergesort_recurse(in_array, left, centre);
mergesort_recurse(in_array, centre, right);
merge(in_array, left, centre, right);
}
}
void merge(int* array, int left, int centre, int right) {
/*Establish the initial indexes of the left and right sides of the two
"halves" to be merged.*/
int l = left;
int r = centre;
int length = right-left;
/*A temporary array to hold the merged data - this implementation is not
in-place*/
int* tmp = malloc(length * sizeof(int));
/*Iterate over the length of the merge.*/
int i;
for(i = 0; i < length; i++) {
if(r==right){
/*If the right index has reached the right hand end of the data, the
remaining elements can be dumped in from the LHS.*/
memcpy(tmp+i, array+l, (length-i)*sizeof(int));
break;
}
else if (l==centre) {
/*Conversely if the left index has reached the LHS end, the
remaining elements can be dumped in from the RHS.*/
memcpy(tmp+i, array+r, (length-i)*sizeof(int));
break;
}
else if(array[l] < array[r]) {
/*Otherwise add from the left or right by comparison.*/
tmp[i] = array[l];
l++;
}
else {
tmp[i] = array[r];
r++;
}
}
/*Finally memcpy the temp array into the target.*/
memcpy(array+left, tmp, length*sizeof(int));
free(tmp);
}回答 2
Code Review用户
发布于 2013-01-30 05:37:16
我不能在这里有太多的错误，这看起来一般都很合理。我认为下面的第一点是最重要的，取决于你对C有多少经验，第二点可能有意义，也可能没有意义。
信息隐藏
首先，您应该将其分成单独的.h和.c文件；也许您已经这样做了，但只是将它们粘贴在一起以供发布。无论哪种方式，如果您想重用这一点，您将需要将您的函数原型放入到#include的头文件中。
当您这样做时，您应该只提供内部函数(即不希望用户直接调用的函数)内部链接。因此，你的两个职能：
void mergesort_recurse(int* in_array, int i, int j);
void merge(int* array, int left, int centre, int right);应以static开头：
static void mergesort_recurse(int* in_array, int i, int j);
static void merge(int* array, int left, int centre, int right);因此，您的标题将类似于：
#ifndef MERGESORT_H_
#define MERGESORT_H_
void mergesort(int *in_array, int len);
#endif //MERGESORT_H_静态函数原型位于.c文件中：
static void mergesort_recurse(int* in_array, int i, int j);
static void merge(int* array, int left, int centre, int right);这防止了除实现者以外的任何人调用merge或mergesort_recurse。这使您可以安全地修改任何static函数，并知道它们不会在任何用户代码中使用--它们的界面可以自由更改，不会破坏任何东西--它们实际上是面向对象的private函数。
泛型排序
你说你想回到C里，我不知道你以前对这门语言有多了解，但通常情况下，排序例程都是通用的。这可能有点复杂，但如果您希望对任何类型进行排序，我将遍历您需要更改的内容。
首先，我们所有的int *都变成了void *。我们还需要添加一个参数，指定我们实际传入的类型的大小。
void mergesort(void *in_array, int len, size_t el_size);下一步是抽象出比较是如何完成的:而不是简单地使用<或>，我们将传递一个函数指针，我们可以将其用作比较函数:它具有签名：
int (*compare)(const void*, const void*);不过，这很难看，所以让我们为其制作一个typedef：
typedef int (*cmp_t)(const void*, const void*);我们还将为交换两个值做同样的事情:这将用于替换
int temp = in_array[right-1];
in_array[right-1] = in_array[left];
in_array[left] = temp;同样，使用typedef：
typedef void (*swap_t)(void *, void *);我们的标题现在看起来是：
#ifndef MERGESORT_H_
#define MERGESORT_H_
typedef int (*cmp_t)(const void*, const void*);
typedef void (*swap_t)(void *, void*);
void mergesort(void *in_array, int len, size_t el_size, cmp_t, swap_t);
#endif //MERGESORT_H_我们在.c：
static void mergesort_recurse
(void* in_array, int i, int j, size_t el_size, cmp_t, swap_t);
static void merge(void *array, int left, int centre, int right, size_t el_size, cmp_t);实现仍然是相当相似的，但是使用void*会使事情变得更加混乱。与if(in_array[left] > in_array[right-1])不同，我们需要调用比较函数，并使用强制转换进行大量操作：
compare(((char *)in_array + (left * el_size)), ((char *)in_array + (right - 1)*el_size)) > 0)人力资源经理，太丑了。让我们创建一个可以为我们完成所有这些转换和索引计算的函数：
在我们的.c文件中：
static void* get_pos(void *array, int index, size_t el_size)
{
return ((char *)array + (index * el_size));
}在此函数中需要更改的唯一其他内容是通过函数指针传递到其他函数：
mergesort_recurse(in_array, left, centre, el_size, compare, swap);
mergesort_recurse(in_array, centre, right, el_size, compare, swap);
merge(in_array, left, centre, right, el_size, compare);在merge中，所有对memcpy的调用都必须改变一点，例如：
memcpy(get_pos(tmp, i, el_size), get_pos(array, r, el_size), (length-i) * el_size);所有这些都允许用户对他们想要的任何东西进行排序--整数、双数、结构等等--只要他们提供自己的比较和交换函数：
int compare_i(const void *a, const void *b)
{
int x = *((int *)a);
int y = *((int *)b);
if(x == y) return 0;
if(x < y) return -1;
return 1;
}
void swap_i(void *a, void *b)
{
int temp = *(int *)a;
*((int *)a) = *((int *)b);
*((int *)b) = temp;
}因此，我们的mergesort调用应该类似于：
int x[] = {5, 8, 2, 3, 1, 7, 10};
mergesort(x, 7, sizeof(int), compare_i, swap_i);如果上面的内容都很让人困惑，我很抱歉，但希望当您进入C的更粗的部分时，它将给您提供一些值得回顾的东西。标准库qsort也使用这些技术作为泛型排序例程，因此理解这些技术将有助于理解标准库的某些部分。
Code Review用户
发布于 2013-01-31 01:01:07
我无法与你从@Yuushi中得到的答案相竞争，但我有一些挑剔和学究的东西要补充。
- C函数通常以第0列中的开头{开头。
- 函数最好是有序的，这样就没有必要使用本地原型了--也就是说，使用顺序相反。
- 我更喜欢在关键字(
if、for、while等)后面加上空格。 - 我喜欢
int *var;而不是int* var;。考虑一下int* var1, var2;-var2不是指针。 - 有一些额外的垂直间距，对我来说，是不可取的。
https://codereview.stackexchange.com/questions/21036
复制相似问题
腾讯云开发者
