多线程排序的一点思考

多线程排序内部使用快速排序算法,但因为排序时,要对数据进行分区,以便避免由于使用锁而降低排序效率。而数据分区时,我们该如何分,什么时间分是一个需要测试和权衡的问题。

QDAC的QDB的数据排序将使用多线程排序,算法不外乎两种:

1、简单分区再排序

在排序前,先将数据进行分块,保证前一块的的所有值都小于后一块,这样子再次将各个块进行分别排序后的结果就是顺序排列的。

2、直接分区排序后合并

先将数据直接切成不同的数据块,然后对数据块的内容进行排序,这样子就得到了一组内部排序好的数据块,最后对排序的结果进行一次合并,得到最终的排序结果。

第一种方法我们在QWorker的示例中进行了测试,大约是直接快速排序的2-3倍左右,第二种方式目前尚未编码验证,我会在近期QDB实现数据排序时,测试两种算法的性能对比,以期为大家选择一个最快的算法。

分享到: