排序是基础算法，快排算法曾经是很多大公司的入职必考，现在很多编程语言的函数库把排序作为标准函数，大多程序员已经不需要自己写排序函数了。
    毫无疑问，经过多年发展，排序算法已经达到最优，基于比较型复杂度是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编辑过]

O(kn) 是什么意思？

大佬之间的较量，作为小白的咱们在这叫喧个啥，静静的跪拜就是小白的工作，
我先吱一声，吱吱《我是来回答你的问题的》
那个应该大概可能也许是空间时间复杂度吧？

哈哈哈，你说的有道理。
我还是想知道 k 是哪里来的，不过应该大概可能也许是误写吧？

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朵   附言：现在除了支持外，更多的是膜拜和

膜拜大佬您啊

计数排序法O(n)描述,我就觉得不对,首先要获得数组最大值要一遍数组，因此，说是O(2n)我觉得比较妥当。

不管是O(2n)还是 O(0.0000001n) 还是O(10000n)
都叫做O(n)算法
首项系数忽略的

[此贴子已经被作者于2020-3-23 01:54编辑过]