d - 元素的就地排序

Question

Phobos 是否有一些可变参数算法来订购 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/eweortsmcmibppmvtriw@forum.dlang.org#post-eweortsmcmibppmvtriw:40forum.dlang.org。

Answer 1

Adam 的解决方案有效，尽管它使用元素的临时副本。对 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

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

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 个参数的排序网络都应该是手写的。

编辑：我完全改变了以前的算法，这实际上是非常低效的。冒泡排序不是最优的，但它实际上适用于排序算法。那里有一些编译指示可以查看已构建的网络。