排序是基础算法，快排算法曾经是很多大公司的入职必考，现在很多编程语言的函数库把排序作为标准函数，大多程序员已经不需要自己写排序函数了。
    毫无疑问，经过多年发展，排序算法已经达到最优，基于比较型复杂度是O(nlogn)，非比较型的可达O(n)。好多编程民科总是自以为发明了宇宙无敌的排序算法，却不知道，你所想的别人早就做过了。
    即使如此，排序算法作为入门算法，仍然有学习的必要，在个性表达上，仍然有优化加速的空间。
    为了让大家直观地看到自己排序函数的优劣，我已经写好框架，各位只要在main函数前面按“void 函数名(double *,int)”的格式写好自己的排序函数，然后在main函数里的f数组中按格式“(int)函数名,函数说明,”顺序添加，程序就能自动执行你的排序函数，并最终指出你的排序速度是c qsort的多少倍（f数组0元素不要占用，它是专用于c qsort的）。

    期待各位的优秀排序算法！

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define maxlen 10000000        //一千万个数据参与排序
struct sort_fun
{
    int fun;                   //排序函数地址
    char info[50];             //排序函数说明
};

int test_sort(double *a,int len)
{//本函数测试数组元素是否有序，有序返回true，无序则返回false
    int i;
    for(i=1;i<len&&a[i]>=a[i-1];i++);            //测试是否为降序
    if(i!=len)for(i=1;i<len&&a[i]<=a[i-1];i++);  //不是降序则测试是否为升序
    return i==len;
}

int cmpp(const void *a, const void *b)
{//c中qsort回调函数用的
    double  c, d;
    c = *(double*)a;
    d = *(double*)b;
    return c>d?1:-1;
}

void c_qsort(double *a,int len)
{//c qsort函数
    qsort(a, len, sizeof(double), cmpp);
}

void sort2(double *a,  int n)
{//分治法排序
    int i, j, k;
    double *b;
    if (n < 2)return;
    sort2(a, n / 2);
    sort2(a + n / 2, n - n / 2);                         //递归分段排序，也可不用递归，用循环完成分段。
    b = (double *)malloc(sizeof(double)*n);              //申请空间
    for (i = k = 0, j = n / 2; i < n / 2 && j < n;)
    {
        if (a[i] < a[j])b[k++] = a[i++];
        else b[k++] = a[j++];
    }
    for (; i < n / 2;)b[k++] = a[i++];
    for (; j < n;)b[k++] = a[j++];                       //两段有序数组合并，需要额外空间
    for (i = 0; i < n; i++)a[i] = b[i];                  //还原合并后的排序结果
    free(b);                                             //释放空间
}

void main()
{
    struct sort_fun f[]=
    {
        (int)c_qsort,"  c qsort函数",
        (int)sort2,"wmf2014分治法",
        /*
        下面可添加自定义排序函数
        格式：(int)自定义排序函数名,排序算法说明(不超过50个字符),
        */
    };
    int i,j,k,m,n = maxlen;
    double *aa,*bb;
    void (*sort_f)(double *,int);  //定义一个函数指针
    aa=(double *)malloc(sizeof(double)*n);
    bb=(double *)malloc(sizeof(double)*n);
    for (i = 0; i < n; i++)
    {
        k = rand() % 10 < 5 ? -1 : 1;   
        aa[i]= k * (double)rand()*rand() / (rand() % 100000 + 15);
    }
    //生成maxlen个随机double数，aa是原始乱序数组，每次复制到bb中排序
    printf("排序总数：%d个。\n",n);
    for(i=0;i<sizeof(f)/sizeof(struct sort_fun);i++)
    {
        k=clock();                                //开始计时
        for(j=0;j<n;j++)bb[j]=aa[j];              //复制原始乱序数据到bb
        sort_f=(void(*)(double *,int))f[i].fun;   //强制转换为函数指针
        sort_f(bb,n);                             //开始排序
        if(!i)m=clock()-k;
        printf("%s",f[i].info);
        if(!test_sort(bb,n))printf(",排序错误");
        else printf(",排序正确");
        printf(",用时：%7d毫秒，速度是qsort的%.2f倍。\n",clock()-k,(double)m/(clock()-k));
    }
    free(aa);
    free(bb);
    system("pause");
}

[此贴子已经被作者于2020-3-11 19:57编辑过]

k取决于数据类型长度，如果是int、float是4个字节，最终要扫描四次，所以时间复杂度就是4n。
我设想的是把任何数据类型当做字节串用计数法排序（计数法复杂度是O(n)），还没想好怎么解决，好像仍然要用递归，空间复杂度不好控制，正负数及指数部分也不好安排排序（3/19 20:30更新：我的思路失败了，用时超过20秒，还排序错误。建议各位学习下松式基排，我的思路和这个类似。）。
今天添加了希尔排序，代码是拷贝别人的。
附各种排序时间空间复杂度表：

[此贴子已经被作者于2020-3-19 20:30编辑过]

我们这防控仍在继续，每天都要到执勤点做出入人员登记，测体温。希望疫情早日结束，各位都正常起来，该上学的上学，该挣钱的挣钱！
今天利用空余时间狠狠啃了下基排，下班后利用一下午的时间写了个通用类型基排函数（松式基排的变种），速度是c qsort的7倍，真的很快。如果不是写通用类型，只排正整数的话，速度可达qsort的25倍，排一千万个数也就300多毫秒，太快了！估计也就计数法排序可以比它快了。有了这个，玩排序也就此打住了，其他的什么桶排、堆排我也了解了下，在常规数据类型排序中肯定没有这个速度快。
基排的精髓就是乾坤大挪移，通过对数据各位计数，得到这个数据在该位上的排位，有几位就挪动该数几次，排序即完成，实在精妙！一般基排是10进制位排，松式基排是一个字节当做一位，也就是256进制排。通常基排只能排正整数，如果了解了IEEE754规范和有符号数规则，基排对负数和浮点数排序也是信手拈来，我写的这个函数可以排序所有常规类型数据。



我是通过反复看这个GIF动画学习基排的

收到的鲜花

• 叶纤 于 2020-03-21 20:47 送鲜花  5朵   附言：现在除了支持外，更多的是膜拜和

2020/6/15 20:45更正：
二次排序由插入排序改成递归后，在桶数为排序总数0.5倍的情况下，排序速度比快排高，如果桶数增加到1倍，还可以提高，再增加桶数速度增加不明显，甚至有些倍数还降低了。

前两天在https://bbs.bccn.net/thread-501938-1-1.html参与了桶排序讨论，今天用代码实现了下，并把它合并到我的不同排序算法比较的代码中。
经过反复优化，发现桶排序虽然属于非比较类型排序，却没有什么优势，通过不断调整桶数，观察到当桶数是被排序数的4倍时，才勉强和c qsort的排序速度相当。
当然，我的算法并不是严格意义上的非比较排序，我在二次排序中用了插入排序。现在正考虑设计一个桶数据结构，让该算法可以使二次排序通过递归调用完成，也许能够提高些速度，预计可以达到分治法排序速度，大概是c qsort的1.4倍。
下图是设置不同桶数时排序速度的变化：





下面是我的桶排序代码，欢迎提供宝贵意见：

void sort7(double *a, int n)
{//桶排序
    const double k = 4;  //定义桶和排序总数的比例
    double *p, dmax, dmin, s;
    int *t, i, j, m, c = (int)(k*n) + 1;       //多设置一个桶，防止误差
    p = (double *)malloc(n * sizeof(double));  //预备一个空间辅助排序
    t = (int*)malloc(c * sizeof(int));         //预备一个空桶
    dmax = dmin = a[0];
    printf("  桶数量是待排序数据的%.2f倍\n", k);
    for (i = 0; i < n; i++)
    {//第一次扫描所有待排序数据，找出其中最大数和最小数，同时将数据转移到预备空间
        if (a[i] > dmax)dmax = a[i];
        if (a[i] < dmin)dmin = a[i];
        p[i] = a[i];
    }
    s = (dmax - dmin) / (double)(c - 1);       //得到每个桶容纳的数据范围基数
    if (s == 0)return;                         //如果基数为0说明待排序数据都相等，无需排序。（double数能否判断等于0，存疑）
    for (i = 0; i < c; i++)t[i] = 0;           //首先将每个桶归零置空
    //第二次扫描所有待排序数组，根据扫描到的数据计算其应该放到哪个桶中，对应桶数据加一。
    for (i = 0; i < n; i++)t[(int)((p[i] - dmin) / s)]++;
    for (i = j = 0; i < c; i++)
    {
        if (t[i])
        {
            j += t[i];
            t[i] = j;                          //确定每个桶的数据上边界位置
            if (j < n)a[j] = dmax + 1;         //上边界处填入不存在的最大数用于判断插入排序停止位置
        }
    }
    for (i = 0; i < n; i++)
    {//第三次扫描所有待排序数据，计算对应桶编号，用桶编号的位置数据作为下标放置待排序数据并执行插入排序
        m = (int)((p[i] - dmin) / s);
        if (t[m])
        {
            for (j = --t[m]; j<n-1&&p[i]>a[j + 1]; j++)
                a[j] = a[j + 1];
        }
        a[j] = p[i];
    }
    free(p);
    free(t);  //释放本函数申请过的内存
}

[此贴子已经被作者于2020-6-15 20:49编辑过]

不是vip用户，那个程序无法看全，粗看应该还有个循环调你那个定分直插函数的。
你自己可以和c函数库的qsort比较，如果能比他快，就很不错。
其实如果不是分治思想，就只是传统插入排序的改进，很难有根本的速度提高，估计排2000万个双精度数需要三天三夜。插入排序的改进版就是希尔排序，通过不断缩小插入排序间隔，使插入排序复杂度尽可能接近O(n)，据测算，希尔排序最好能做到O(n^1.3)。
就单纯的排序速度提高上来说，最快的就是桶排序算法了（基数排序、计数排序都是桶排序的一种），在实数范围内排序基数排序最快，其次是桶排（你可以看我11楼的演示图，排2000万个double类型数，基排比qsort快近7倍，桶排也可做到2.5倍）。这类排序空间复杂度是O(n)，空间换时间。

如果测试一万个int数就花了70毫秒，那我建议你的代码不要叫改进了，叫改退。普通的插入排序排11111个int数我只花0.043秒（测试电脑为惠普学生本，i5-4200u,主频1.60G，8G内存，win10 64位系统，很低档的）。测试排序算法速度，数据量不到一千万以上，没有测试意义，如果以复杂度O(n^2)来测试这个量的数据，我感觉用时是无穷大，反正我曾经等了三个钟头没有得到结果，只好终止了。我的插入排序代码如下，供你参考：

void sort_i(int *a, int n)  //n为排序数据总数
{//插入排序
    int i, j;
    int t;
    for (i = 1; i < n; i++)
    {
        t = a[i];
        for (j = i; j > 0 && t < a[j - 1]; j--)
            a[j] = a[j - 1];
        a[j] = t;
    }
}

[此贴子已经被作者于2020-10-9 19:24编辑过]