Hexo

---

前言

什么?你说归并？？？
开了个1百万的数据量，差点以为是鲁大师点烟。

一、测试结果对比

使用的是win10的子系统ubuntu编译运行

计算时间使用的是< cstdlib>里的clock()函数，因为数量很小，所以最后结果没除CLOCKS_PER_SEC

基数排序会快一些，但是消耗空间接近2倍更多。
2倍，才2倍？
我参考了这个优化—链接

二、附上代码，大家可以自己手动测试测试

language-cpp

#include<iostream>
#include<cstdio>
#include<ctime>
#include<algorithm>
#include<cstdlib>
using namespace std;

int getMax(int* p,int len)
{
   
    int m=p[0];
    for(int i=1;i<len;++i)
    {
   if(p[i]>m){
   m=p[i];}}
    return m;
}

void count_sort(int* p,int len,int cot)
{
   
    int temp[len];//不报错？？？
    int buckets[10]={
   0};
    for(int i=0;i<len;++i)
    {
   buckets[(p[i]/cot)%10]++;}
    for(int i=1;i<10;++i)
    {
   buckets[i]+=buckets[i-1];}
    for(int i=len-1;i>=0;--i)
    {
   
        temp[buckets[(p[i]/cot)%10]-1]=p[i];
        buckets[(p[i]/cot)%10]--;
    }
    for(int i=0;i<len;++i)
    {
   p[i]=temp[i];}
}


int main()
{
   
    srand((unsigned)time(NULL));
    clock_t start,end;
    int arr[100];
    int len=100;
    for(int i=0;i<len;++i)
    {
   arr[i]=rand()%len;}

    start=clock();

    //count_sort
    int maxA=getMax(arr,len);
    for(int cot=1;maxA/cot>0;cot*=10)
    {
   count_sort(arr,len,cot);}

    //sort(arr,arr+len);

    end=clock();
    printf("\ntime=%.6lf\n",(double)(end-start));//CLOCKS_PER_SEC
    // for(int i=0;i<len;++i)
    // {printf("%d ",arr[i]);}

    return 0;
}