0

目前正在尝试学习D编程语言。

编写了这个小快速排序算法，它在使用随附的示例运行时返回 OutOfMemoryError。

import std.stdio;
import std.algorithm;

int[] qs(int[] ary) 
{
    if(ary.length <= 1)
    {
        return ary;
    }

    int pivot_pos   = 0;
    int pivot       = ary[pivot_pos];

    for(int i = 0; i < ary.length; i++) 
    {
        if(ary[i] < pivot) 
        {
            ary = ary.remove(i) ~ ary;
            pivot_pos++;
        }
        else 
        {
            ary ~= ary.remove(i);
            if(i < pivot_pos)
                pivot_pos--;
        }
    }

    return qs(ary[0..pivot_pos]) ~ qs(ary[(pivot_pos+1)..ary.length]);
}

int main() 
{

    int[] ary = [ 2, 1, 4, 1, 6, 78, 3, 5, 10, 129, 234, 3, 5 ];

    ary = qs(ary);

    foreach(int element; ary) 
    {
        printf("%d ", element);
    }

    return 0;
}

任何提示如何解决这个问题或算法中有什么问题？有什么技巧可以学习 D 以及我必须关心什么？

4

1 回答 1

5

您正在使用连接。这将每次分配一个新数组（唯一一次不会是当数组之外有未分配的内存时），并且您对数组进行分区的方式会保留对足够部分的引用，以使 GC 无法将它们全部扫描

你应该使用交换：

auto tmp=ary;
while(tmp.length) 
{
    if(tmp[0]==pivot)break;//assumes unique
    if(tmp[0]<pivot) 
    {
        tmp=tmp[1..$];
        pivot_pos++;
    }
    else 
    {
        swap(tmp[0],tmp[$-1]);
        tmp=tmp[0..$-1];
    }
}

或者只使用std.algorithm.partition它的来源可以在这里找到

于 2013-04-27T19:37:24.230 回答