d - 元素的就地排序

Question

火卫一是否有一些可变参数算法来对l值引用参数进行排序？类似的东西

int a=3;
int b=2;
int c=1;
orderInPlace(a,b,c);
// a is now 1
// b is now 2
// c is now 3

还有一个函数变体，比如order(a, b, c)，返回元组也会很好。

如果没有，我想我们应该利用std.algorithm:swap.

另请参阅 http://forum.dlang.org/thread/[e-mail]#post-eweortsmcmibppmvtriw:40forum.dlang.org。

Answer 1

亚当的解决方案有效，尽管它使用了元素的临时副本。通过对 std.algorithm 进行小的修改，可以编写一个就地对元素进行排序的版本：

import std.algorithm;
import std.stdio;
import std.traits;
import std.typecons;
struct SortableRef(T)
{
    private T * _p;
    @property ref T value() { return *_p; }
    alias value this;
    void opAssign(T * value) { _p = value; }
    @disable void opAssign(SortableRef!T value);
    void proxySwap(SortableRef!T other) { swap(*_p, *other._p); }
}
template PointerTo(T) { alias T* PointerTo; }
void orderInPlace(T...)(ref T values)
    if (!is(CommonType!(staticMap!(PointerTo, T)) == void))
{
    alias CommonType!T E;
    SortableRef!E[values.length] references;
    foreach (i, ref v; values)
        references[i] = &v;
    references[].sort();
}
void main()
{
    int a=3;
    int b=1;
    int c=2;
    orderInPlace(a, b, c);
    writeln([a, b, c]);
}

但是，仅当传递给orderInPlace的值很大、不可分配或无法复制时才实用。

Answer 2

我不认为火卫一有，但你可以像这样制作自己的：

void orderInPlace(T...)(ref T t) {
    import std.algorithm;
    T[0][T.length] buffer;
    foreach(idx, a; t)
        buffer[idx] = a;
    auto sorted = sort(buffer[]);
    foreach(idx, a; t)
        t[idx] = sorted[idx];
}

std.algorithm，sort需要一个数组，但这很容易 - 我们将元组复制到堆栈数组中，对其进行排序，然后将信息复制回元组。所以也许不完美，但它会起作用。您可以通过仅返回 t 而不是执行 ref 来使其正常运行。

Answer 3

考虑到参数数量少，并且它们的数量是编译时已知的（没有循环条件），这里的排序网络可能是最有效的。

气泡排序非常适合被网络化排序。我把这个放在一起。它有效并且非常简单：

import std.stdio, std.string;
void bubbleSort(T...)(ref T values)
{
    static if (T.length > 1)
    {
        foreach(I, _; T[0 .. $ - 1])
        {
            pragma(msg, format("[%s %s]", I, I + 1));
            compareAndSwap(values[I], values[I + 1]);
        }
        bubbleSort(values[0 .. $ - 1]);
    }
}
void compareAndSwap(T)(ref T a, ref T b)
{
    import std.algorithm;
    if(a > b)
        swap(a, b);
}
void main()
{
    int a =  10;
    int b =  30;
    int c =  11;
    int d =  20;
    int e =   4;
    int f = 330;
    int g =  21;
    int h = 110;
    shellSort(a, b, c, d, e, f, g, h);
    writefln("%s %s %s %s %s %s %s %s!", a, b, c, d, e, f, g, h);
}

虽然说实话，如果这是标准库，任何少于 10 个参数的排序网络都应该是手写的。

编辑：我完全改变了以前的算法，这实际上是非常不恰当的。气泡排序不是最佳的，但它实际上适用于排序算法。里面有一些编译指示，可以看到构建的网络。