c - 这个冒泡排序怎么这么快？

Question

我遇到了一种速度快得离谱的冒泡排序算法……比如在 0.03 秒内以相反的排序顺序对 100,000 个全长整数进行排序。我知道冒泡排序被认为是最低效的排序算法之一，那么是什么让它变得更好呢？

我看到，如果在第一次通过时没有交换任何项目(意味着它已经排序)，它会停止排序，但这不应该影响倒序的情况。

附注谁能想出一种方法来更快地对这么多整数进行排序？也许基数排序？

void sort(int list[], int n)
{
    int i; 
    int j; 
    int gap;
    int swapped = 1;
    int temp;
    gap = n;

    while (gap > 1 || swapped == 1)
    {
        gap = gap * 10 / 13;
        if (gap == 9 || gap == 10)
        {
            gap = 11;
        }
        if (gap < 1)
        {
            gap = 1;
        }
        swapped = 0;
        for (i = 0, j = gap; j < n; i++, j++)
        {
            if (list[i] > list[j])
            {
                temp = list[i];
                list[i] = list[j];
                list[j] = temp;
                swapped = 1;
            }
        }
    }
}

Answer 1

如评论所述，它是 comb sort .

对于就地排序，quick sort或 heap sort会更快。如果使用第二个临时数组，则 merge sort或 counting / radix sort更快。计数/基数排序应该是其中最快的。

计数/基数排序的示例代码。在我的系统(Intel 2600K，3.4ghz)上大约需要 0.001 秒。这个示例代码可以稍微优化一下(比如使用 mIndex[j] 的指针)，但我不确定编译器是否已经完成了大部分优化，您可以通过较小的代码更改进行优化。处理器开销可能非常小，以至于内存带宽成为限制因素。

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);
}