桶排序

叁歲伎倆 2022-04-23 01:34 226阅读 0赞

#include <stdio.h> 
    
    void swap(int *a, int *b)
    
    {
    
        int temp = *a;
    
        *a = *b;
    
        *b = temp;
    
    }
    
    int partition(int *array, int low, int high)
    
    {
    
        int middle = (low + high)/2;
    
        for(int i=low,j=high; i<j; ) {
    
            while(array[i] < array[middle]) ++i;
    
            if(i < j && i != middle) {
    
                swap(&array[i], &array[middle]);
    
                middle = i;
    
            }
    
            while(array[j] > array[middle]) --j;
    
            if(i < j && j != middle) {
    
                swap(&array[j], &array[middle]);
    
                middle = j;
    
            }
    
        }
    
        return middle;
    
    }
    
    int quicksort(int *array, int low, int high)
    
    {
    
        int piovt_pos;
    
        if(low < high) {
    
            piovt_pos = partition(array, low, high);
    
            quicksort(array, low, piovt_pos - 1);
    
            quicksort(array, piovt_pos + 1, high);
    
        }
    
    }
    
    struct barrel {
    
        int a[10];
    
        int count;
    
    };
    
    int main()
    
    {
    
        int data[] = {23, 12, 3, 54, 1, 98, 24, 34};
    
        int min = data[0];
    
        int max = data[0];
    
        for(int i=1; i<sizeof(data)/sizeof(int); ++i) {
    
            min = min < data[i] ? min : data[i];
    
            max = max > data[i] ? max : data[i];
    
        }
    
        int num = (max - min + 1)/10 + 1;
    
        barrel *pBarrel = new barrel[num];
    
        for(int i=0; i<sizeof(data)/sizeof(int); ++i) {
    
            int j = (pBarrel+((data[i]-min+1)/10))->count;
    
            (pBarrel+((data[i]-min+1)/10))->a[j] = data[i];
    
            (pBarrel+((data[i]-min+1)/10))->count++;
    
        }
    
        static int pos = 0;
    
        for(int i=0; i<num; ++i) {
    
            quicksort((pBarrel+i)->a, 0, (pBarrel+i)->count-1);
    
            for(int j=0; j<(pBarrel+i)->count; ++j) {
    
                data[pos++] = (pBarrel+i)->a[j];
    
            }
    
        }
    
        for(int i=0; i<8; ++i) {
    
            printf("%d ", data[i]);
    
        }
    
        return 0;
    
    }

简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。

例如要对大小为\[1..1000\]范围内的n个整数A\[1..n\]排序

可以把桶设为大小为10的范围，具体而言，设集合B\[1\]存储\[1..10\]的整数，集合B\[2\]存储

(10..20\]的整数，……集合B\[i\]存储(   (i-1)\*10,   i\*10\]的整数，i   =   1,2,..100。总共有

100个桶。

然后对A\[1..n\]从头到尾扫描一遍，把每个A\[i\]放入对应的桶B\[j\]中。

然后再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任

何排序法都可以。最后依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这

样就得到所有数字排好序的一个序列了。

假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果

对每个桶中的数字采用快速排序，那么整个算法的复杂度是

O(n   +   m   \*   n/m\*log(n/m))   =   O(n   +   nlogn   -   nlogm)