今天想做测试各个排序算法运行时间比较的程序，来对这几天学的排序算法小结一下。所以我先生成了1000000个1~150之间的随机数存到文件里。然后做了一个测试运行时间的程序。想看一下结构。但是结果效果并不太好。实践中，自己做的qsort函数和mergesort函数并没有理想中的那么快。

结果是这样：（可能并不准确，但却是是运行结果）

库函数快速排序：0.139000 seconds

自制快速排序：0.375000 seconds

归并排序：0.358000 seconds

堆排序：0.525000 seconds

计数排序：0.032000 seconds

插入+归并排序：0.313000 seconds

显然，除了线性复杂度的计数排序，其他的都比系统自带的库函数运行的慢。

因此得出以下结论：

1.懂了算法思想并不一定能做出最棒的程序。

2.以后排序首选系统自带库函数和计数排序，其他的排序算法可以当作思想来借鉴。

 

那么排序算法大体就到这里。下一节一开始讲的是最值的选法。

从n个数里选出最小值。复杂度下界是n

从n个数里选出最大值。复杂度下界也是n

但是，从n个数里同时选出最小值和最大值，算法导论给出了复杂度(3/2)n的优化算法。

就是通过一个一个的比较改成一对一对的比较

     每次找两个数，先比较这两个数，然后让较大值与当前的最大值比较，让较小值与当前最小值比较。这样优化之后，原来每两个数要比较4次，现在只需要比较3次，所以复杂度优化成了原来的3/2 。

代码今天就先不打了，这个问题比较简单。可能需要分n为奇数还是偶数讨论一下。

 

PS：下面是测试排序时用到的生成随机数和测试时间的代码。

#include
     
      #include
      
       #include
       
        int *makerandom(int n,int x){    int *a=(int *)malloc((n+1)*sizeof(int));    srand(time(0));    int i;    for (i=1;i<=n;i++) {        a[i]=rand()%x+1;    }    return a;}
       
      
     

#include
     
      #include
      
       #include
       
        int main(){    long i=100000000L;    clock_t start,finish;    double duration;    start=clock();    /*while (i--);*/  //测试时间的代码     finish=clock();    duration=(double)(finish-start)/CLOCKS_PER_SEC;    printf("%lf seconds\n",duration);    return 0;}