易语言版sort排序数组易语言源码和c++的sort相比

在debug模式下, 易语言耗时大概是20秒左右
而c++耗时是4秒左右, 慢了5倍左右

release模式下

易语言耗时大概7秒
c++耗时500毫秒
比c++慢了14倍左右…..

易语言核心库的数组排序耗时600毫秒左右

这个排序的优点就是可以自行扩展, 支持排序自定义数据类型, 需要自己写比较自定义数据类型大小的函数
可以只排序部分成员, 不一定要排序整个数组

想扩展自定义排序的话, 自己写一个类, 继承 sort_base 类
然后重写 size 和 cmp 这两个方法
size方法是单个成员在数组里占用的尺寸
指针加减的时候会根据这个尺寸计算

cmp方法是比较两个成员的大小, 内部的排序算法就是靠这个返回值进行排序的

STL的std::sort函数是基于Musser在1996年提出的内省排序(Introspective sort)算法实现。这个算法是个缝合怪,它汲取了插入排序、堆排序以及快排的优点:

针对大数据量,使用快排,时间复杂度是O(NlogN);
若快排递归深度超过阈值__depth_limit ,改用堆排序,防止快排递归过深,同时保持时间复杂度仍是O(NlogN);
当数据规模小于阈值_S_threshold时,改用插入排序。

发表回复

后才能评论