对“平滑”二维数组项进行排序的最快方法

我希望Timsort能赢,因为它利用了数据中的“运行”。

快速排序通常会很快,但有可能遇到最坏的情况。例如,当给定已排序的输入时,Quickshort的某些版本为O(n^2)。如果有人给了你一个错误的渐变填充图像,那就不太友好了……

这是一个有点疯狂的想法-你也可以试试Z-排序通行证( Wikipedia link )它能让你在两个维度上利用相邻的相似颜色。

我先从原地快速移动开始。浮点比较在大多数处理器上都很快(当然要比mergesort所需的分配快得多)。

我在平面阵列上使用numpy的排序例程,在一些图像上构建了一个快速而肮脏的基准。这是对几百张随机图像和几百张人脸图像的平均值。两者都是单精度的。

On random images...
quicksort took 0.000153 seconds per image.
mergesort took 0.000170 seconds per image.
heapsort took 0.000241 seconds per image.
On real images...
quicksort took 0.000136 seconds per image.
mergesort took 0.000143 seconds per image.
heapsort took 0.000230 seconds per image.

所有的算法似乎都受益于现有的部分排序,特别是快速排序。numpy似乎没有排序列表合并功能,所以我不能尝试对行进行预排序,唉。

有Timsort,但我在一些地方看到它是用于比较缓慢的应用程序的;numpy devs显然决定不费心实现它:

http://mail.scipy.org/pipermail/scipy-dev/2009-May/011929.html

可以合并单独排序的行,然后合并排序的行。

这至少可以利用二维数组的一些特殊结构,即单调运行通常会在数组的边缘开始和停止。它还公开了另外两个并行级别。