2_11基数排序

C++的queue实现

class RadixSort {
    public:
        int* radixSort(int* A, int n) {
            // write code here
            for(int i=0; i<4; i++){
                vector< queue<int> > range(10);
                for(int j=0; j<n; j++){
                    range[A[j] / (int)pow(10,i) % 10].push(A[j]);
                }
                int p = 0;
                for(int k=0; k<10; k++){
                    while(!range[k].empty()){
                        A[p] = range[k].front();
                        range[k].pop();
                        ++p;
                    }
                }
            }
            return A;
        }
};

C++ vector 实现

class RadixSort {
    public:
        int* radixSort(int* A, int n) {
            // write code here
            for(int i=0; i<4; i++){
                vector< vector<int> > range(10);
                for(int j=0; j<n; j++){
                    range[A[j] / (int)pow(10,i) % 10].push_back(A[j]);
                }
                int p = 0;
                for(int k=0; k<10; k++){
                    for(int l=0; l<range[k].size(); l++){
                        A[p] = range[k][l];
                        ++p;
                    }
                }
            }
            return A;
        }
};

python 实现

# -*- coding:utf-8 -*-

class RadixSort:
    def radixSort(self, A, n):
        # write code here
        # max_num = max(A)
        for ex in range(0,4):
            radix = [[] for i in range(10)]
            for val in A:
                radix[val/(10**ex)%10].append(val)
            A = []
            for arr in radix:
                A.extend(arr)
            #A = [A.extend(arr) for arr in radix]
        return A