归并排序：如果其中一个数字是 2 个字节，如何排序

Question

我正在尝试使用 void* 进行合并排序。如果我保留数字，我想将其排序为 1 字节，那么它工作得很好。但是，如果数字超过 1 个字节，则效果不佳。我相信它把它当作2个数字。我用数字 500 进行了测试，最后我有 256 和 244 未排序....

#include "msort.h"
#include <iostream>

using namespace std;

void Mergesort( void* base, size_t nelem, size_t width,
                    int (*fcmp)( const void*, const void* ) )
{
    if (nelem <=1)
        return;

    int lhsnelem = nelem/2; 
    int rhsnelem = nelem - lhsnelem;
    char* midpoint = (char*)(base) + ((nelem/2)*width);

    cout << "width is: " << width << endl;

    Mergesort(base, lhsnelem, width, fcmp);
    Mergesort(midpoint, rhsnelem, width, fcmp);

    //ItemType* temp= new ItemType[nelem];
    int temp[20];
    char* lhs = (char*)(base);
    char* rhs = midpoint;
    char* end = rhs + (rhsnelem*width);        
    int count = 0;

    while ((lhs != midpoint) && (rhs != end))
    {
         int num = fcmp( lhs, rhs ); 
         if (num <= 0)
         {
             temp[count] = *lhs;
             lhs = lhs + width;
         }
         else
         {
             temp[count] = *rhs; 
             rhs = rhs + width;
         }
         count++; 
    }

    if (lhs == midpoint)
    {
        while (rhs != end)
        {
            temp[count] = *rhs;
            rhs = rhs + width;
            count++;
        }
    }
    else
    {

        while (lhs != midpoint) 
        {
            temp[count] = *lhs; 
            lhs = lhs + width;
            count++;
        }

    }

    for (int i=0; i<nelem; i++)
    {
        lhs = (char*)(base)+ (width*i);
        *lhs = temp[i];
        lhs = lhs + width;
    }
}

main.cpp

/////// main.cpp ///////////////////////
// here is my comparison function in main.cpp

int compare(const void *one, const void *two)
{
    if (*(int*)one > *(int*)two) return 1;
    if (*(int*)one < *(int*)two) return -1;
    return 0;
}

1 字节数字的输出正常：

In:    5 8 7 4 1 6 11 41 160 47 38 120 40 58 12 43 66 98 17 140
Out:   1 4 5 6 7 8 11 12 17 38 40 41 43 47 58 66 98 120 140 160

如果有 2 字节数字则输出不正常，排序不正确效果不好：

In:    500 50 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Out:   256 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 50 244

Answer 1

您面临的直接问题是您正在使用 char *lhs 来复制整数。在进行复制之前，您需要将指针转换回 int *。

#include <iostream>

using namespace std;

static void Mergesort(void *base, size_t nelem, size_t width,
                      int (*fcmp)(const void *, const void *))
{
    if (nelem <= 1)
        return;

    int lhsnelem = nelem/2; 
    int rhsnelem = nelem - lhsnelem;
    char* midpoint = (char*)(base) + ((nelem/2)*width);

    Mergesort(base, lhsnelem, width, fcmp);
    Mergesort(midpoint, rhsnelem, width, fcmp);

    int temp[20];
    char* lhs = (char*)(base);
    char* rhs = midpoint;
    char* end = rhs + (rhsnelem*width);        
    int count = 0;

    while ((lhs != midpoint) && (rhs != end))
    {
        int num = fcmp(lhs, rhs); 
        if (num <= 0)
        {
            temp[count] = *(int *)lhs;          // Here!
            lhs += width;
        }
        else
        {
            temp[count] = *(int *)rhs;          // Here!
            rhs += width;
        }
        count++; 
    }


    while (rhs != end)
    {
        temp[count] = *(int *)rhs;          // Here!
        rhs = rhs + width;
        count++;
    }
    while (lhs != midpoint) 
    {
        temp[count] = *(int *)lhs;          // Here!
        lhs = lhs + width;
        count++;
    }

    for (int i = 0; i < nelem; i++)
    {
        lhs = (char *)(base)+ (width*i);
        *(int *)lhs = temp[i];                  // Here!
        lhs = lhs + width;
    }
}

测试代码

static int compare(const void *one, const void *two)
{
    if (*(int*)one > *(int*)two) return 1;
    if (*(int*)one < *(int*)two) return -1;
    return 0;
}

#define DIM(x) (sizeof(x)/sizeof(*(x)))

int array1[] = { 5, 8, 7, 4, 1, 6, 11, 41, 160, 47, 38, 120,
                 40, 58, 12, 43, 66, 98, 17, 140 };
int array2[] = { 500, 50, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                 0, 0, 0, 0, 0, 0, 0, 0 };

static void PrintArray(int *array, size_t n_items)
{
    const char *pad = "";
    for (size_t i = 0; i < n_items; i++)
    {
        cout << pad << array[i];
        pad = ", ";
    }
    cout << endl;
}

int main()
{
    PrintArray(array1, DIM(array1));
    Mergesort(array1, DIM(array1), sizeof(array1[0]), compare);
    PrintArray(array1, DIM(array1));

    PrintArray(array2, DIM(array2));
    Mergesort(array2, DIM(array2), sizeof(array2[0]), compare);
    PrintArray(array2, DIM(array2));

    return 0;
}

你很不幸使用的是little-endian（Intel）机器；如果您使用的是大端机器（SPARC、PPC），您将获得小数量测试用例的零数组。

还有一个更严重、更深层的问题。该代码实际上只能用于对最多 20 个整数的数组进行排序，因为 int temp[20]; （它将大小限制为 20，并将类型限制为 int）并且由于“固定”分配。

分配应替换为内存移动（可能调用 memmove()），这又意味着代码仅适用于 POD（普通数据）类型。 temp 数组需要分配为适当大小 (nelem * width) 的字节数组。而且内存分配很糟糕；它会减慢代码速度。 “也许是个好消息”是，将临时数组复制到原始数组上的最终循环可以用 memmove() 替换。

目前尚不清楚这是不是好的 C++ 代码 - 我认为模板化的实现会更明智。作为C代码，解决了内存移动问题就可以了。

通用代码

static void Mergesort(void *base, size_t nelem, size_t width,
                      int (*fcmp)(const void *, const void *))
{
    if (nelem <= 1)
        return;

    int lhsnelem = nelem/2; 
    int rhsnelem = nelem - lhsnelem;
    char* midpoint = (char*)(base) + ((nelem/2)*width);

    Mergesort(base, lhsnelem, width, fcmp);
    Mergesort(midpoint, rhsnelem, width, fcmp);

    char *temp = new char[nelem * width];
    char* lhs = (char*)(base);
    char* rhs = midpoint;
    char* end = rhs + (rhsnelem*width);        
    int count = 0;

    while ((lhs != midpoint) && (rhs != end))
    {
        int num = fcmp(lhs, rhs); 
        if (num <= 0)
        {
            memmove(&temp[count], lhs, width);
            lhs += width;
        }
        else
        {
            memmove(&temp[count], rhs, width);
            rhs += width;
        }
        count += width;
    }

    while (rhs != end)
    {
        memmove(&temp[count], rhs, width);
        rhs += width;
        count += width;
    }
    while (lhs != midpoint) 
    {
        memmove(&temp[count], lhs, width);
        lhs += width;
        count += width;
    }

    memmove(base, temp, nelem * width);
    delete[] temp;
}