基础算法-桶排序

女爷i 2022-07-28 05:07 126阅读 0赞

# 原理 #

设数组中要排序的数字有n个，为十进制数即r=10（这里RADIX=10）即十个桶其索引为0~9，数字的最大长度为k即数字最大k位十进制数，设置每个桶可装载d个数字（这里BUCKETSIZE=100）。  
步骤一：使用最低位优先法，取每个数字的最低位数字当做索引，分别放置到对应索引的桶中，即桶排序分配过程。  
步骤二：从索引0~9的桶中依次（先进先出）拿出数字，并放置到原数组中，即桶排序的收集过程。  
步骤三：取每个数字的次低位数字当做索引，进行分配和收集过程。  
步骤四：直到取到数字最大长度d位的数字，进行分配和收集过程后，元素组即为排序完成后的数据。

桶排序是一种**稳定**的排序算法，其时间最坏的复杂度为O((r+n)\*d)。从原理中可以看到桶排序是可在线性时间排序，但空间复杂度为O(rd+n)

# 实现 #

最低位优先(Least Significant Digit first)法，简称LSD 法。

#include<stdio.h>
    
    #define RADIX 10
    #define BUCKETSIZE 100
    
    int bucket[RADIX][BUCKETSIZE];
    
    // 这里把-1当做结束标志，这里桶排序无法排序包含-1的负数，仅排序包含0和正整数；可以设置其他标志如MAX_INT等来解决这类问题
    void clearBucket() {
            for (int i = 0; i < RADIX; ++i) {
                    for (int j = 0; j < BUCKETSIZE; ++j)
                            bucket[i][j] = -1;
                    // 或使用memset
            }
    
    }
    
    // 分配数组中数字到各桶时间复杂度O(nd)，空间复杂度O(n+rd)
    void distribute(int a[], int n, int k) {
            for (int i = 0; i < n; ++i) {
                    // 求每个整数的第10^(k-1)位置上的数（如k=2，则求得十位上的数字；k=3，则求得百位上的数字）
                    int radix = a[i];
                    for (int l = 0; l < k; l++)
                            radix /= RADIX;
                    radix %= RADIX;
    
                    // 根据上面求得的radix值，把相应的整数放在各自对应的桶中 
                    int j = 0;
                    while (bucket[radix][j] != -1)
                            j++;
                    bucket[radix][j] = a[i];
            }
    }
    // 收集桶中的数据，存放到原数组中时间复杂度为O(rd),空间复杂度为O(n+rd)
    void collect(int a[], int n) {
            int k = 0;
            for (int i = 0; i < RADIX; ++i) {
                    int j = 0;
                    while (bucket[i][j] != -1) {
                            a[k] = bucket[i][j];
                            j++;
                            k++;
                    }
            }
    }
    
    // 这里桶排序按照“先低位后高位”的方式排列每个整数，即最低位优先（LSM）
    // a[] : 要排序的数组
    // n : 排序数组的大小
    // k : 要排序数字的最大长度或者位数 
    void radixSort(int a[], int n, int k) {
            for (int i = 0; i < k; ++i) {
                    distribute(a, n, i);
                    collect(a, n);
                    clearBucket();
            }
    }
    
    void print(int a[], int n) {
            for (int i = 0; i < n; ++i)
                    printf("%d ", a[i]);
            printf("\n");
    }
    
    int main() {
            clearBucket(bucket, RADIX, BUCKETSIZE);
            int a[] = {
       10, 2, 123, 4, 58, 39, 222, 715, 14, 0, 148};
            unsigned int size = sizeof(a)/sizeof(a[0]);
            print(a, size);
            // k=3,要排序的数字最大长度为3位
            radixSort(a, size, k);
            print(a, size);
            return 0;
    }