博客

我们假设要对一个数组进行排序，排序的key值为32位整数类型。那么可以使用快速排序对数组进行排序，但快速排序虽然简单易用，但它的平均情况和最坏情况复杂度是不同的。平均情况下，快速排序的时间复杂度为O(nlogn)，空间复杂度为O(logn)【分配给递归调用时的堆空间】；最坏情况下，快速排序的时间复杂度为O(n2)，空间复杂度为O(n)。但如果要排序的是整型key值，就可以利用桶排序对其按位分配，使其时间复杂度保证为O(n)，空间复杂度为O(1)。

光解释难以清除，一看代码便清楚了。

void qsort_bucket(int s[], int n)
{
    qsort_bucket_inner(s, 0, n-1, 31);
}


void qsort_bucket_inner(int s[], int low, int up, int bit_level)
{
    int m, i;
    int bit_value, tmp;
    if(low >= up || bit_level < 0) return;

    bit_value = 1<<bit_level;
    m = low-1;
    for(i=low; i<=high; i++){
        if((s[i] & bit_value) == 0){
            tmp = s[i];
            s[i] = s[++m];
            s[m] = tmp;
        }
    }
    qsort_bucket_inner(s, low, m, bit_level-1);
    qsort_bucket_inner(s, m+1, up, bit_level-1);
}

这段代码排序的时间复杂度为O(32n) = O(n)，空间复杂度为O(32) = O(1)。虽然只适用于以整型线索排序的情况，但简单实用，

可以适用于各种情况，不会有特别坏的情况出现。这段代码还可以用两边互换的方法优化，只是会复杂一点。

它是参照了桶排序的情况，只是如果从位0增加到位31，用快排的方式肯定失败了，而从位31到位0，则恰好可以。