学步园

自己写的C++ STL Algorithm中qsort的实现如下：

void swap(void *a, void *b, int size)
{
    unsigned char *bytesOfA = reinterpret_cast<unsigned char*>(a);
    unsigned char *bytesOfB = reinterpret_cast<unsigned char*>(b);
    char tmp = 0;
    for(int i = 0; i < size; ++i)
    {
        tmp = *(bytesOfA+i);
        *(bytesOfA+i) = *(bytesOfB+i);
        *(bytesOfB+i) = tmp;
    }
}

int partition(void *base, int num, int size, int (*comparator)(const void *, const void *))
{
    int first = 0, end = num-1;
    while(first < end)
    {
        while(first < end && comparator(base+first*size, base+end*size) <= 0)
        {
            --end;
        }
        if(first < end)
        {
            swap(base+first*size, base+end*size, size);
            ++first;
        }
        while(first < end && comparator(base+first*size, base+end*size) <= 0)
        {
            ++first;
        }
        if(first < end)
        {
            swap(base+first*size, base+end*size, size);
            --end;
        }
    }
    return first;
}

void qsort(void *base, int num, int size, int (*comparator)(const void *, const void *))
{
    if(num > 0)
    {
        int pivot = partition(base, num, size, comparator);
        qsort(base, pivot, size, comparator);
        qsort(base+(pivot+1)*size, num-pivot-1, size, comparator);
    }
}

用poj2388题测试，时间、内存比用STL的qsort还要略少一点，可能是数据不大的原因吧，STL里的qsort可以对非常大的内存空间排序，应该是迭代实现的。