排序算法比较

#include<iostream>
#include<iomanip>
#include<vector>
#include<cstring>
using namespace std;

//快速排序
//unstable
//time:   sita(n*lgn)   omiga(n*lgn)   O(n^2)
//memery  O(lgn)
void quicksort(int *a, int *b){  //[a,b)
    int *l = a , *r = b-1;
    if(l>=r)return;
    int *mid = l; //suppose that the little some is in [l,mid-1] and bound is in mid
    while(r>mid){
        if(*r<*l)swap(*(++mid),*r);
        else r--;
    }
    swap(*l,*mid);
    quicksort(a,mid);
    quicksort(mid+1,b);
}


//插入排序
//stable
//time:   sita(n^2) omiga(n)  O(n^2)
//memery: O(1)
void insertionsort(int *a,int *b){
    for(int *i = a; i<b; i++){
        int *j = i;
        while(j>a&&*j<*(j-1)){//可能每次都直接跳出去，结果成了omiga(n)
            swap(*j,*(j-1));
            j--;
        }
    }
}


//选择排序
//unstable
//time:   sita(n^2) omiga(n^2)  O(n^2)
//memery: O(1)
void selectsort(int *a,int *b){
    for(int *i=a;i<b;i++){
        int*min = i;
        for(int *j=i+1;j<b;j++){
            if(*min>*j)min=j;
        }
        swap(*min,*i);
    }
}


//基数排序??
//unstable
//time:   omige(log(k,maxvalue)*n)  O(log(k,maxvalue)*n)
//memery:
void radixsort(int*a,int*b){
    const int k =15;
    vector<int>bin[2][k+1];// 滚动数组
    int t=0;
    
    for(int*i=a;i<b;i++)bin[t][(*i)&k].push_back(*i);
    t^=1;
    
    for(int times=1;times<8;times++){
        for(int i=0;i<=k;i++)bin[t][i].clear();
        for(int i=0;i<=k;i++){
            for(int x:bin[t^1][i]){
                bin[t][(x>>(4*times))&k].push_back(x);
            }
        }
        t^=1;
    }
    for(int i=0;i<k;i++){
        for(int x:bin[t^1][i]){
            *(a++)=x;
        }
    }
}


//计数排序??
//unstable
//time:   sita(maxvalue-minvalue) omiga(maxvalue-minvalue) O(maxvalue-minvalue)
//memery: O(maxvalue-minvalue)
void countingsort(int*a,int*b){
    int maxvalue = (1<<31); // 最小的int
    int minvalue = -1^(1<<31);// 最大的int
    for(int*i=a;i<b;i++){
        maxvalue=max(maxvalue,*i);
        minvalue=min(minvalue,*i);
    }
    int*data = new int[maxvalue-minvalue+1];
    memset(data,0,sizeof(int)*(maxvalue-minvalue+1));
    for(int*i=a;i<b;i++)data[(*i)-minvalue]++;
    for(int i=minvalue;i<=maxvalue;i++){
        while(data[i-minvalue]--)*(a++)=i;
    }
    delete[] data;
}


//桶排序??
//time:   sita(k*O(sort(n/k))  omiga(k*O(sort(n/k))  O(k*O(sort(n/k))
//memery:
void bucketsort(int*a,int*b){
    int maxvalue = (1<<31); // 最小的int
    int minvalue = -1^(1<<31);// 最大的int
    for(int*i=a;i<b;i++){
        maxvalue=max(maxvalue,*i);
        minvalue=min(minvalue,*i);
    }
    if(maxvalue==minvalue)return;
    const int k = 10;
    vector<int>data[k];
    for(int*i=a;i<b;i++){
        int belong = ((*i)-minvalue)/((maxvalue-minvalue)/10+1);
        data[belong].push_back(*i);
    }
    for(int i=0;i<k;i++){
        sort(data[i].begin(),data[i].end());
        for(int x:data[i])*(a++)=x;
    }
}


//冒泡排序
//stable
//time： sita(n^2) omiga（n） O(n^2)
//memery: O(1)
void bubblesort(int*a,int *b){
    for(int i=0;i<b-a;i++){
        bool noswap = true;
        for(int*j=a+1;j<b-i;j++){
            if(*(j-1)>*j){
                swap(*(j-1),*j);
                noswap = false;
            }
        }
        if(noswap)break;
    }
}


//归并排序
//stable
//time:   sita(n*lgn) omiga(n*lgn) O(n*lgn)
//memery: O(n)
void mergesort(int*a,int*b){
    int*mid = a+ (b-a)/2; // =(a+b)/2
    if(a>=b-1)return;
    
    mergesort(a,mid);
    mergesort(mid,b);
    
    int*c=new int[b-a];
    int*pa=a,*pm=mid,*pc=c;
    while(pa<mid&&pm<b){
        *(pc++)=*pa<=*pm?*(pa++):*(pm++);
    }
    while(pa<mid)*(pc++)=*(pa++);
    while( pm<b )*(pc++)=*(pm++);
    memcpy(a,c,sizeof(int)*(b-a));
}


//希尔排序
//unstable
//time:   sita(n^1.3) omiga(??) O(n^2)
//memery: O(1)
void shellsort(int*a,int*b){
    for(int gap=(b-a)>>1;gap;gap>>=1){//枚举gap
        for(int*i=a+gap;i<b;i++){
            int x=*i,*j=i;
            while(j-gap>=a&&x<*(j-gap)){
                *j=*(j-gap);
                j-=gap;
            }
            *j=x;
        }
    }
}


//堆排序
//unstable
//time:   sita(n*lgn)   omiga(n*lgn)   O(n*lgn)
//memery: O(1)
void heapsort(int*a,int*b){
    const int n=b-a;
    a--;
    
    //up
    for(int i=1;i<=n;i++){//建立大根堆
        int j=i;
        while(j!=1&&a[j]>a[j>>1]){//不是根且比父亲大
            swap(a[j],a[j>>1]);
            j>>=1;
        }
    }
   
    //down
    for(int i=n;i>=1;i--){
        swap(a[1],a[i]);
        int cur = 1;
        while((cur<<1)<i){//左儿子存在
            int son = (cur<<1|1)<i && a[cur<<1|1]>a[cur<<1];//若满足此条件则son为1，代表着右儿子优先
            if(a[cur]<a[cur<<1|son])swap(a[cur],a[cur<<1|son]);
            else break;//若优先的儿子都不能换
            cur = cur<<1|son;
        }
    }
}


const int n = 1e4;
int ans[n];

inline void compare(int *a,int *b,void sort(int*,int*),string name){
    int data[n];
    memcpy(data,a,sizeof(int)*(b-a));
    time_t begin = clock();
    sort(data, data+n);
    time_t spend = clock()-begin;
    cout<<setw(16)<<std::left<<name<<" time:"<<setw(13)<<spend;
    //check it
    for(int i=0;i<n;i++){
        if(ans[i]==data[i]&&i==n-1)cout<<"everything is right"<<endl;
        else if(ans[i]!=data[i]){
            cout<<"error"<<endl;
            break;
        }
    }
}

int main(){
    srand(int(time(NULL)));

    int a[n];
    for(int i=0;i<n;i++)a[i]=rand()%9000000+1000000;
    memcpy(ans,a,sizeof(a));
    sort(ans,ans+n);
    
    compare(a,a+n,sort,"* STL(fastest)");
    compare(a,a+n,quicksort,"quicksort");
    compare(a,a+n,insertionsort,"insertionsort");
    compare(a,a+n,selectsort,"selectsort");
    compare(a,a+n,radixsort,"radixsort");
    compare(a,a+n,countingsort,"countingsort");
    compare(a,a+n,bucketsort,"bucketsort");
    compare(a,a+n,bubblesort,"bubblesort");
    compare(a,a+n,mergesort,"mergesort");
    compare(a,a+n,shellsort,"shellsort");
    compare(a,a+n,heapsort,"heapsort");
    
    puts("ok");
}



/*
 
 输出:
 
 * STL(fastest)   time:468          everything is right
 quicksort        time:1265         everything is right
 insertionsort    time:178130       everything is right
 selectsort       time:126705       everything is right
 radixsort        time:3128         everything is right
 countingsort     time:50445        everything is right
 bucketsort       time:1002         everything is right
 bubblesort       time:355497       everything is right
 mergesort        time:3295         everything is right
 shellsort        time:3960         everything is right
 heapsort         time:2347         everything is right
 ok
 
 
 */