优化排序

Question

我一直在寻找最快的算法来对 1,000,000 个整数进行排序。到目前为止，令人惊讶的是，C 的内置 qsort 函数似乎是我尝试过的所有函数中最快的（我已经测试了预排序、反向排序和随机输入文件）。平均而言，前后排序大约需要 0.07 秒，随机大约需要 0.2 秒。

如何将其优化为运行更快？有什么快速的技巧吗？我知道 C++ 的 std 排序更快，但是不能在 C 中使用...我附上了我的代码。

int compare(const void *x, const void *y){   
   return ( *(int*)x >= *(int*)y );
}

qsort(list, 1000000, sizeof(int), compare);

Answer 1

在我的系统（Intel 2600K 3.4ghz）上，这种计数/基数排序将在大约 0.01 秒内对 1,000,000 个 32 位无符号整数进行排序，但它使用与原始数组 (pData) 大小相同的第二个数组 (pTemp) ), 所以它需要两倍的内存。

typedef unsigned int UI32;

UI32 * RadixSort(UI32 * pData, UI32 * pTemp, size_t count)
{
size_t mIndex[4][256] = {0};            // index matrix
UI32 *pDst, *pSrc, *pTmp;
size_t i,j,m,n;
UI32 u;

    for(i = 0; i < count; i++){         // generate histograms
        u = pData[i];
        for(j = 0; j < 4; j++){
            mIndex[j][(size_t)(u & 0xff)]++;
            u >>= 8;
        }       
    }
    for(j = 0; j < 4; j++){             // convert to indices
        n = 0;
        for(i = 0; i < 256; i++){
            m = mIndex[j][i];
            mIndex[j][i] = n;
            n += m;
        }       
    }
    pDst = pTemp;                       // radix sort
    pSrc = pData;
    for(j = 0; j < 4; j++){
        for(i = 0; i < count; i++){
            u = pSrc[i];
            m = (size_t)(u >> (j<<3)) & 0xff;
            pDst[mIndex[j][m]++] = u;
        }
        pTmp = pSrc;
        pSrc = pDst;
        pDst = pTmp;
    }
    return(pSrc);
}

对于有符号整数，用于索引时只需要补整数的符号位即可：

typedef          int  I32;
typedef unsigned int UI32;

I32 * RadixSort(I32 * pData, I32 * pTemp, size_t count)
{
size_t mIndex[4][256] = {0};            // index matrix
UI32 *pDst, *pSrc, *pTmp;
size_t i,j,m,n;
UI32 u;

    for(i = 0; i < count; i++){         // generate histograms
        u = pData[i];
        for(j = 0; j < 4; j++){
            if(j != 3)                  //  signed integer handling
                mIndex[j][(size_t)(u & 0xff)]++;
            else
                mIndex[j][(size_t)((u^0x80) & 0xff)]++;
            u >>= 8;
        }       
    }
    for(j = 0; j < 4; j++){             // convert to indices
        n = 0;
        for(i = 0; i < 256; i++){
            m = mIndex[j][i];
            mIndex[j][i] = n;
            n += m;
        }       
    }
    pDst = (UI32 *)pTemp;               // radix sort
    pSrc = (UI32 *)pData;
    for(j = 0; j < 4; j++){
        for(i = 0; i < count; i++){
            u = pSrc[i];
            if(j != 3)                  //  signed integer handling
                m = (size_t)(u >> (j<<3)) & 0xff;
            else
                m = (size_t)((u >> (j<<3))^0x80) & 0xff;
            pDst[mIndex[j][m]++] = u;
        }
        pTmp = pSrc;
        pSrc = pDst;
        pDst = pTmp;
    }
    return((I32 *)pSrc);
}

优化排序

Optimizing qsort

c

algorithm

sorting

optimization

qsort