original sort algorithm:queuesort

The method of this algorithm is to enqueue and dequeue for several time in certain order to implement the sort.

Data Preparation:

queue<int> Q[10]; 
queue<int> nums; //use to store numbers that need to be sorted

STEP 1:
We need to find the number which obtains the maximum number of bits.Then we use mBit to store this information.
In this step,we can get this information during the input procedure.

STEP 2:
We do a loop from 1 to mDigits.Each time we push the number that in nums to certain queue in Q.The ‘certain’ means the number on certain bit of the number.
For EXAMPLE: 123.
The first time: Because the number on the first digit of 123 is 3,we push it to Q[3];
The second time: Because the number on the second digit of 123 is 2,we push it to Q[2];
The third time: Because the number on the third bit of 123 is 1,we push it to Q[1];
if it isn’t the number who obtains the maximum number of digit.There will be a fourth time.But 123 doesn’t have the fourth bit,so we push it to Q[0].
Then:
We scan from Q[0] to Q[9] and add all number back to nums. Then go to the second loop.

TestData:
4
123 132 321 1
FirstTime:
Nums:123 132 321 1
Queue0:NULL
Queue1:321 1
Queue2:132
Queue3:123
…(Other queues do not have element)

SecondTime:
Nums:321 1 132 123
Queue0:1
Queue1:321
Queue2:123
Queue3:132

ThirdTime:
Nums:1 321 123 132
Queue0:1
Queue1:123 132
Queue2:NULL
Queue3:321

Sort Complete:Nums 1 123 132 321

Apparently,the complexity is related to the max length of the maximum number.So the worst complexity is O(9N^2)->All number is the same.And the average complexity is $theta$(9N*logN).
The advantage of this algorithm is that it ignores the discrete degree of the number.But if the value of the difference the number of bits of maximum number and the minimum number is very bit and there are few numbers in the sequence,this algorithm is not that efficient.

#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define INF 0xfffffffff;
typedef long long Lovelive;
queue<Lovelive> Q[10];
queue<Lovelive> nums;
Lovelive ts[10001];
Lovelive N;

Lovelive mbit;

inline void init(){
    memset(ts,0,sizeof(ts));
    mbit=0;
}

bool cmp1(Lovelive a,Lovelive b){
    return a>b;
}

inline void getBit(Lovelive aa){
    while(aa){
        aa/=10;
        mbit++;
    }
}

inline Lovelive power(Lovelive x,Lovelive n){
    if(n==0) return 1;
    else{
        while((n&1)==0){
            n>>=1;
            x*=x;
        }
    }
    Lovelive result=x;
    n>>=1;
    while(n!=0){
        x*=x;
        if((n&1)!=0)
            result*=x;
        n>>=1;
    }
    return result;
}

inline Lovelive getIdx(Lovelive n,Lovelive time){
    Lovelive mod = power(10,time);
    if(n*10<mod) return 0;
    Lovelive num=n%mod;
    while(num>=10){
        num/=10;
    }
    return num;
}


inline void work(){
    for(Lovelive i=1;i<=mbit;i++){
        printf("Step %lld.n",i);
        while(!nums.empty()){
            Lovelive tp=nums.front();
            nums.pop();
            Q[getIdx(tp,i)].push(tp);
        }
        for(Lovelive j=0;j<=9;j++){
            if(Q[j].empty()){
                printf("Queue%lld:n",j);
            }else{
                queue<Lovelive> tmps;
                while(!Q[j].empty()){
                    tmps.push(Q[j].front());
                    Q[j].pop();
                }
                printf("Queue%lld:",j);
                while(!tmps.empty()){
                    printf("%lld ",tmps.front());
                    nums.push(tmps.front());
                    tmps.pop();
                }
                cout<<"n";
            }
        }
    }
    while(!nums.empty()){
        printf("%lld ",nums.front());
        nums.pop();
    }
}

int main(){
    init();
    cin>>N;
    Lovelive maxNumber=-1000000000;
    for(Lovelive i=0;i<N;i++){
        Lovelive tp;
        scanf("%lld",&tp);
        nums.push(tp);
        maxNumber=max(maxNumber,tp);
    }
    getBit(maxNumber);
    work();
    return 0;
}