JavaScript快速排序中的無限遞歸？

這是我寫的quicksort代碼。該功能不起作用，因爲它無法到達基本情況。如果我將密鑰r和l記錄到控制檯，則無論調用sort函數多少次，它們都保持不變。所以我想知道l，r這個參數是否真的作爲數據傳入函數。爲什麼發生？JavaScript快速排序中的無限遞歸？

function sort(data){ 
    if(data.length < 2){ 
     return data; 
    } 
    else{ 
     var l = []; 
     var r = []; 
     var pivot = parseInt(data.length/2); 
     for(i=0; i<data.length; i++){ 
      if(data[i] > data[pivot]){ 
       r.push(data[i]); 
      } 
      else{ 
       l.push(data[i]); 
      } 
     } 
     return sort(l).concat(sort(r)); 
    } 
}

來源

2013-02-07 Yujun Wu

您正在覆蓋l和r的每次遞歸調用。你應該在你的排序功能之外初始化它們。 – marteljn

@marteljn是的。但是如果我在返回之前放置console.log（l），它會打印相同的數組。所以我很困惑 –

我必須問：只調用'originalArray.sort（）'有什麼問題？ –

327

我認爲這裏的問題是您的分區步驟不一定會縮小輸入數組。例如，讓我們跟蹤如果嘗試排序會發生什麼[1，2]。在這種情況下，您的主元素將是元素2.由於1> 2爲假，因此1會添加到列表l。由於2> 2爲假，因此將2添加到列表l。因此，列表l上的遞歸調用將與您的原始調用具有完全相同的參數，導致無限遞歸。

要解決此問題，請嘗試將輸入拆分爲三個列表 - 其中一個較小的值，一個相等的值和一個更大的值。此代碼如下所示：

function sort(data){ 
    if (data.length < 2){ 
    return data; 
    } else { 
    var l = []; 
    var r = []; 
    var e = []; 
    var i = 0; 
    var pivot = (data.length/2) | 0; 

    for(i = 0; i < data.length; i++) { 
     if (data[i] > data[pivot]) { 
     r.push(data[i]); 
     } else if (data[i] < data[pivot]) { 
     l.push(data[i]); 
     } else { 
     e.push(data[i]); 
     } 
    } 
    return sort(l).concat(e, sort(r)); 
    } 
}

這個新版本明確的羣體平等的元素融入到自己的列表，以便它們不會遞歸無論是遞歸調用的排序。它也優雅地處理重複的元素。

希望這會有所幫助！

來源

2013-02-07 21:20:43 templatetypedef

+1。有點改進：'sort（l）.concat（e，sort（r））;' – Bergi

@ Bergi-謝謝！我絕不是JS程序員，我不知道你可以這樣做。 – templatetypedef

gg Randall。讓我們通過'sort'標籤獲取API訪問調用的一些統計信息？ :) –

JavaScript通過引用傳遞對象（數組也是對象）。如果您想按值傳遞它們，則需要使用拼接功能，如here所述。

請注意，這會創建大量的數據副本。你可能想要使用本地sort（）函數。

來源

2013-02-07 21:23:21 nus

我不認爲這是這裏的問題。無限遞歸不是因爲傳遞引用，而是由於原始代碼無法正確處理需要處理的其中一種情況。 – templatetypedef

你的問題沒有提到無限遞歸的任何事情，而是關於變量不會改變... – nus

如果選擇數組的最大值作爲主元素，則data的所有值都將以數組l結尾，而在r中則不會。因此會使遞歸永不停止（並且保持l,r和pivot爲相同的值）。除非這是一次腦部運動，否則使用data.sort()應該做得更好。 ;）

來源

2013-02-07 21:25:24

JavaScript快速排序中的無限遞歸？

回答

相關問題