通用快速排序不工作

Question

我想做一个通用快速排序功能，我不明白我在做什么，因为它不能正常工作。
这里是我的代码：

typedef bool (*CmpFunction)(void*, void*); 

void swap(void *c1, void *c2) 
{ 
    assert(c1 && c2); 
    int c = *(int*)c1; 
    *(int*)c1 = *(int*)c2; 
    *(int*)c2 = c; 
} 

void quick_sort(void* a, int n, CmpFunction swap) 
{ 
    int p, b = 1, t = n - 1; 
    if (n < 2) 
     return; 
    swap((char*)a, (char*)a+n/2); 
    p = *(int*)a; 
    while(b <= t) { 
     while(t >= b && (char*)a + t >= p) 
     t--; 
     while(b <= t && (char*)a + b < p) 
     b++; 
     if (b < t) 
     swap((char*)a+(b++), (char*)a+(t--)); 
    } 
    swap((char*)a, (char*)a+t); 
    quick_sort(a, t, swap); 
    n=n-t-1; 
    quick_sort(a + t + 1, n, swap); 
} 

虽然原来的快速排序功能，无需我试图使它通用是：

void quick_sort(int a[], int n) 
{ 
    int p, b = 1, t = n - 1; 
    if (n < 2) 
     return; 
    swap(&a[0], &a[n/2]); 
    p = a[0]; 
    while(b <= t) { 
     while(t >= b && a[t] >= p) 
     t--; 
     while(b <= t && a[b] < p) 
     b++; 
     if (b < t) 
     swap(&a[b++], &a[t--]); 
    } 
    swap(&a[0], &a[t]); 
    quick_sort(a, t); 
    n=n-t-1; 
    quick_sort(a + t + 1, n); 
} 

void swap(int *c1, int *c2) 
    { 
     int c = *c1; 
     *c1 = *c2; 
     *c2 = c; 
    } 

我使用这个主（）：

int main(){ 

    char b[] = {'a','t','b','c','y','s'}; 
    int c[] = {1,4,6,3,5,7}; 
    quick_sort(c, 6, &swap); 

    for (int i=0;i<6;i++) 
     printf("%d | ", c[i]); 

    return 0; 
} 

现在我们都同意输出应该是：

1, 3, 4, 5, 6, 7 

这确实是我运行NOT generic函数时得到的结果。
当我运行我的通用（上）功能，我基本上垃圾。

大家有什么想法我错了吗？ :)

Answer 1

最明显的问题：你的输入数据是一个int数组，类型强制转换成一个void *指针，然后被迫进入一个char *指针：

swap((char*)a, (char*)a+n/2); 

在这里，你强制将进入一个char *指针，并跳入n/2。
char *是一个1字节大小的元素的数组
int *是一个由2,4或8字节大小的元素组成的数组，取决于编译器/ OS/CPU。

所以char * a +1，void给出了初始数组第一个元素的第二个字节。

Answer 2

你正在尝试做一些C语言不太适合的东西。如果你想这样做，你需要一些关于pointer arithmetics的背景知识。

具体地，对于T *，其中T是具有大小N（sizeof(T) == N）一个类型，

T * ptr; 
ptr = (T *) 0x0100; 
ptr = ptr + 1; 
// ptr now has value 0x100 + N 

这意味着你可以没有，这将在数据阵列操作而无需知道尺寸的通用函数数组元素。

因此，我建议您重写您的quick_sort和swap函数以合并size参数。然后，您将指针指向char *并使用size参数使功能正常工作。示例swap函数如下。

void swap(void * c1, void * c2, size_t size) { 
    char tmp[size]; // temporary buffer big enough to contain c1 data 
    memcpy(tmp, c1, size); 
    memcpy(c1, c2, size); 
    memcpy(c2, tmp, size); 
} 

修改quick_sort留作锻炼:)。但请记住，当你不知道你的数据的大小，则必须使用memcpy(dst, src, size)代替dst = src，你必须使用memcmp(a1, a2, size) >= 0的a1 >= a2，而不是和你的指针访问必须由size相乘（exerpt从quick_sort如下）：

编辑：@Schwern在评论中指出为什么使用memcmp()可能无效。比较未知大小和格式的值（endianness，float X int）可能需要一个通用比较函数（这可能几乎不可能写入）。这让我们回到C不适合这项任务。

void quick_sort(void *a, int n, size_t size) { 
    char[size] p; 
    int b = 1, t = n - 1; 
    if(n < 2) 
     return; 
    // Using new swap with 'size' parameter 
    swap(&a[0], &((char *)a)[n/2 * size], size); 
    // or swap((char *)a + 0, (char*)a + (n/2 * size), size); 
    memcpy(p, a, size); 
    while(b <= t) { 
     while(t >= b && memcmp((char *)a[t * size], p, size) >= 0) { 
    ... 
} 

然后，您可以编写包装宏来将size参数传递给quick_sort函数。

#define QSORT(arr, n) quick_sort((arr), (n), sizeof((arr)[0])) 

Answer 3

qsort是一个通用的排序功能。你给它一个数组，数组元素的大小，元素的数量和一个比较函数。

typedef int(*compare)(const void*, const void*); 

void quicksort(void *base, size_t num_elements, size_t width, compare *cmp); 

要通过阵列排序功能需要知道每个元件的宽度，因此可以正确地执行指针移动算术。一个数组char将为每个元素1个字节。 int的数组可能是4个字节。 double将为8. char阵列的base[4]为base + 4*1，但是对于int阵列它是base + 4*4。最终base[n]是base + (n * width)。

为避免对元素中的数据做出假设，或者希望对它们进行排序，compare用于比较排序元素。它返回< 0如果a < b,0如果a == b和> 0如果a > b。这使得它可以像大多数号码一样简单，如return a - b。

比较整数一个例子功能：

int cmp_int(const void* _a, const void* _b) { 
    /* Do the casting separately for clarity */ 
    int *a = (int *)_a; 
    int *b = (int *)_b; 

    return *a - *b; 
} 

没有必要在一个交换功能来传递。只要您知道单个交换功能将提供的元素大小即可。从@HonzaRemeš' answer作品。

void swap(void * a, void * b, size_t size) { 
    /* Temp buffer large enough to contain an element */ 
    char tmp[size]; 

    memcpy(tmp, a, size); 
    memcpy(a, b, size); 
    memcpy(b, tmp, size); 
} 

有了这一切记住，你的功能是不是报错元件尺寸（即width），所以它不能正确通过阵列移动。它也不必要地传递一个swap函数，但如果知道元素的大小，则不需要这样做。而且你缺乏适当的比较功能来比较元素。没有太多的通用排序功能，如果它不能比较的东西排序。