試圖在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不會掃描它們全部

你應該使用交換：

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它的它的來源可以發現here