BucketSort.cpp

# include<iostream>
# include<vector>

using namespace std;

int GetHighBit(vector<int>& arr,int size){
    int maxnum=arr[0];
    for(int i=0;i<size;i++){
        maxnum=max(maxnum,arr[i]);
    }
    int bit=1;
    while(maxnum>10){
        maxnum/=10;
        bit++;
    }
    return bit;
}

//时间复杂度 O(n + k);
void BucketSort(vector<int>& arr,int size){
    int highbit=GetHighBit(arr, size);
    int redix=1;
    vector<int> count(10,0);
    vector<int> res=arr;
    for(int i=1;i<=highbit;i++){
        for(int j=0;j<10;j++)count[j]=0;
        for(int j=0;j<size;j++){
            int index=(arr[j]/redix)%10;
            count[index]++;
        }
        for(int j=0;j<9;j++){
            count[j+1]=count[j+1]+count[j];
        }
        for(int j=size-1;j>=0;j--){
            int index=(arr[j]/redix)%10;
            res[count[index]-1]=arr[j];
            count[index]--;
        }
        vector<int> tmp=arr;
        arr=res;
        res=tmp;
        redix*=10;
    }
}


int main(){
    vector<int> arr={1,2,110,2,40,482,93,40,2,20,59,99};
    BucketSort(arr,arr.size());
    for(int i=0;i<arr.size();i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}