c++ - 快速排序 3 个值

Question

我有一个包含三个浮点值的数组，我想按升序对它们进行排序(尽管任何排序算法的顺序都可以很容易地反转)。调用 std::sort 似乎有点矫枉过正:

float values[3] = {...};
std::sort(values, values + 3);

你可以这样做:

float sorted[3] = {min(values), values[0] + values[1] + values[2] -
    min(values) - max(values), max(values)};

但这看起来很丑陋。此外，数字的加减可能会改变中间排序元素的值。而且它不容易就地工作。也很有趣:

float sorted[3];
/*for(int i = 0; i < 3; ++ i) { // unroll
    sorted[(values[i] > values[0]) + (values[i] > values[1]) +
        (values[i] > values[2])] = values[i];
}*/ // this is broken, does not work if two or all values are equal
sorted[(values[0] > values[1]) + (values[0] > values[2])] = values[0];
sorted[(values[1] >= values[0]) + (values[1] > values[2])] = values[1];
sorted[(values[2] >= values[0]) + (values[2] >= values[1])] = values[2];

但这取决于如何将比较结果转换为整数(可能是比较+标志加载指令)。还取决于编译器如何优化每个元素与其自身的比较，如果您考虑特殊的浮点值，这并不容易。也不能就地工作。

#define cswap(a,b) do { if(a > b) { float tmp = a; a = b; b = tmp; } } while(0)
cswap(values[0], values[1]);
cswap(values[1], values[2]);
cswap(values[0], values[1]);

可能有一个排序网络，但我认为除了两个元素的幂之外，这不是排序的最佳选择。只有三个元素......似乎应该有一种非常简单的方法来做到这一点，但也许没有。

对三个数字进行排序的最小且同时快速的方法是什么？可读性在这里不是问题。

这有点类似于 Fastest sort of fixed length 6 int array但在这里我希望有一些简短但快速的代码，因为与对任意数量的项目进行排序循环相比，对 3 个值进行排序可能会用更少的代码行编写。

结果:

在 Intel Core i7-2620M 和 Windows 7 上测量了 1000 亿个数字。Visual Studio 2008，release，数字是用 rand() 生成的，但是减去了里面花费的时间。

std::sort method: 3.510 sec
min/max method: 2.964 sec
comparison insertion: 2.091 sec (the fixed version, 2.292 for the buggy one)
sort3() by Jarod42: 1.966 sec
sorting network: 1.903 sec

Answer 1

一般的算法是:

if (a[0] > a[1])
    swap(a[0], a[1]);
if (a[0] > a[2])
    swap(a[0], a[2]);
if (a[1] > a[2])
    swap(a[1], a[2]);