c - 堆排序适用于字符串，但不适用于整数

Question

我正在尝试让通用堆排序工作。它与字符串完美配合，但由于某种原因不适用于整数类型。完全不知道这是为什么。我确信比较函数是正确的。堆排序函数中的最后一个 if 语句是为了纠正有时会导致第 0 号和第 1 号索引颠倒的错误。

#include "heapsort.h"                                                          
#include <stdio.h>                                                             
#include <assert.h>                                                            
#include <string.h>                                                            
#include <stdlib.h>                                                            
#include <ctype.h>                                                             
#include <sys/types.h>                                                         

int heapsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *)) 
{                                                                              
    int i;                                                                     
    int j;                                                                     

    printf("\n");                                                              
    /*build heap*/                                                             

    for (j = 1; j < nel; j++) {                                                
        i = j;                                                                 
        while (compar(base + i * width, base + (i-1)/2 * width) > 0) {         
            swap(base + i * width, base + (i-1)/2 * width);                    
            i = (i-1)/2;-                                                      
        }                                                                      
    }                                                                          

    /*sort*/                                                                   

    for (i = 1; i < nel; i++) {                                                
        swap(base , base + (nel - i) * width);                                 
        j = 0;                                                                 

        while (((2 * j + 1) < nel - i) && ((2 * j + 2) < nel - i)){            
            if (compar(base + (j * 2 + 2) * width, base + (j * 2 + 1) * width) > 0 
            &&  compar(base + j * width, base + (j * 2 + 2) * width) < 0)      
            {                                                                  
                swap(base + j * width, base + (2 * j + 2) * width);            
                j = 2 * j + 2;                                                 
            }                                                                  
            else if (compar(base + (j * 2 + 2) * width, base + (j * 2 + 1) * width) <= 0 
                  && compar(base + j * width, base + (j * 2 + 1) * width) < 0) 
            {                                                                  
                swap(base + j * width, base + (2 * j + 1) * width);            
                j = 2 * j + 1;                                                 
            }                                                                  
            else                                                               
                break;                                                         
        }                                                                      

    }                                                                          

    if (compar(base + 0 * width, base + 1 * width) > 0) {                      
        swap(base + 0 * width, base + 1 * width);                              
    }                                                                          

    return 0;                                                                  
}                                                                              


void swap(void *a, void *b)                                                    
{                                                                              
    void *temp;                                                                
    printf("swapping %d and %d\n", *(int*)a, *(int*)b);                        
    temp = *(void**)a;                                                         
    *(void**)a = *(void**)b;                                                   
    *(void**)b = temp;                                                         
}

int intcmp(const void * a, const void * b)
{
    return *(int*)a - *(int*)b;
}  

Answer 1

swap 函数看起来不对。假设 a 和 b 引用的值是指针(如果类型是 [const] char * 字符串，则该指针有效)并且是交换 sizeof(void *) 字节。您的系统上可能有 sizeof(int) != sizeof(void *)。

您需要交换宽度字节。