[第一讲] 快速排序算法

楚香饭

我这里找了三个快速排序算法。

楼主这个，我称为 QuickSortMod，Intel Fortran 扩展的 Qsort，以及 Juli Rew（Fortran.com）写的（http://www.fcode.cn/code_prof-38-1.html）

用的 IVF for windows XE2013 SP1 编译，win7sp1 运行。

一些N长度与耗时的曲线如图（X轴为N数据量，Y轴为耗时 mSec ）：


我很奇怪Intel Fortran 的 Qsort 为啥后面斜率变低了，实验了多次。很是奇怪。数据量稍低时，JuliRew的算法效率高，数据量大时，IVF所带的QSort表现不错。

但是这三者又各有优点：
QuickSortMod，允许有其他数组随之而排序，而其他两者只允许一个数组排序。这可能是影响它效率发挥的原因。
IVF扩展的QSort，支持各种数据类型，包括用户自己的 type 类型。（需指定数据单个所占的字节数，需书写外部比较函数）自己书写外部比较函数，可以实现类似时间日期的排序。但通用性不好，只能在 VF 上使用。
JuliRew 算法，简单，高效，代码精炼。

最后，提个题外话，如果数据中已有一定的顺序，比如：1，2，3，7，4，5，6，8，9。用堆排序效率很高。

楚香饭

aliouying 发表于 2014-3-2 20:51
若楼上仔细看下我的算法，其实我的算法就是冒泡排序算法，只是我的程序做了太多的IF用于判断后面跟随的扩 ...

呵呵，确实没有仔细看。
只大致看了接口处。快速排序就是根据冒泡算法修改的，所以有相似之处。

楚香饭

pasuka 发表于 2014-3-4 20:43
为啥不考虑直接上C的代码呢？利用iso c binding 写几个interface即可

做这点计算，Fortran还是足以应对的。

楚香饭

山大克鲁士 发表于 2014-5-26 14:02
快排纵然好理解，但是个人总感觉递归的效率可能不高，正如Davis将所有递归利用压栈弹栈来操作一样，虽然在 ...

递归一定会慢的。尤其是局部变量比较多的函数。

如果不考虑编译器的优化作用的话。