试图在D中编写Quicksort,得到OutOfMemoryError

Question

目前正在尝试学习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以及我需要关心的任何提示？

Answer 1

你正在使用串联.这将每次分配一个新的数组(唯一的时间不会是数组之外的未分配内存),并且对数组进行分区的方式会保留对GC无法扫描所有部分的足够部分的引用

你应该使用swap:

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,它的来源可以在这里找到