在这种情况下递归如何工作？

var arr = [7,3,28,8,9,13,1500,45];

function qsort(a) {
    if (a.length == 0) return [];

    var left = [], right = [], pivot = a[0];

    for (var i = 1; i < a.length; i++) {
        a[i] < pivot ? left.push(a[i]) : right.push(a[i]);
    }

    return qsort(left).concat(pivot, qsort(right));
}

alert(qsort(arr));

该例程使用Quicksort算法对数组进行排序。问题是基本情况ѭ1将如何成立才能停止递归？

已邀请:

7 个回复

喷乡顾沥沪

if (a.length == 0) return [];

当length为0时停止。

挂帘妈乡

传递给递归调用的数组总是比传递给函数的数组小至少一个，因为它不包含数据透视元素。因此，您最终遇到了a.length == 0的基本情况，然后返回而没有递归。

芦歉竭皑

只记得： pivot是数组中的第一项 left是低于pivot的物品 right是高于pivot的物品所以第一次有qsort( [7,3,28,8,9,13,1500,45] )：

left=[3]      pivot=7      right=[28,8,9,13,1500,45]

现在在the4ѭ和right数组上递归调用qsort()。让我们看一下left，那么so14ѭ：

left=[]       pivot=3        right=[]

再次，在“ 4”和“ 6”数组上递归调用“ 10”。再次让我们看一下left，所以so20ѭ： qsort()的第一件事是什么？

if (a.length == 0) return [];

如果它接收到一个空数组（在此执行此操作），它将仅返回一个空数组，从而停止该分支上的执行。因为每次调用“ 10”都会从数组中弹出第一项，所以每次调用“ 10”时，接收到的数组会越来越短，直到将一个空数组发送到“ 10”。另一种思考方式：可能令人困惑的部分是，“ 10”将第一个项目剔除，然后将数组的其余部分分为2个部分。试想一下，如果它没有拆分数组，而是将第一个项目删除了。该函数实际上没有做任何事情，只是用Array的其余部分递归地调用自身。

function recursive_test( arr ) {
    if( arr.length === 0 ) { return []; } // empty Array? Just return.

    var first_item = arr.shift();      // first item in the Array (the head)
                            // now \"arr\" represents the remainder (the tail)

    return recursive_test( arr );  // Just send the \"tail\" to the same function
                                   //   so the next time through, the Array is 
}                                  //   shorter by 1

因此，当您调用该函数时，将发生以下情况：

var array = [5,2,8,3,6,9,0];  // original Array

recursive_test( array );  

// the first time it gets the full Array
// [5,2,8,3,6,9,0]

// but then it pops the first item off, and calls itself with the \"tail\" of the Array
// [2,8,3,6,9,0]

// again it calls itself, just with the \"tail\"
// [8,3,6,9,0]

// and again, and again, and again...
// [3,6,9,0]
// [6,9,0]
// [9,0]
// [0]
// []

// The last time it gets an empty Array. 
// The function sees that it gets an empty Array, and just returns, 
//   halting the recursion

函数中发生了完全相同的事情，除了递归地传递\“ tail \”而不是\“ head \”和\“ tail \”之外，您得到的是\“ head \”（pivot）和一个\“ tail \”，它分为2个数组（left和right）。尾巴的两个部分都发送给递归调用，将其头部弹出，将其余部分拆分，然后再次进行，直到没有剩余。

春驹晴陪

在快速排序中，您采用的是分而治之的方法-而不是立即解决整个问题，而是将问题分成两半，解决每一半，然后将答案合并在一起。要解决问题的每半部分，我们只需递归调用快速排序-即，我们将问题再次分成两半，直到我们不能再进一步分解它为止。线：

if (a.length == 0) return [];

因此，现在我们将其分成了半数次，并解决了所有这些问题，我们可以将它们合并在一起。这行：

return qsort(left).concat(pivot, qsort(right));

说“把左边的子问题和右边的子问题粘在一起，这就是我的答案”。这种气泡上升到顶部，将所有不同的子数组粘在一起，并生成带有答案的数组。比这要复杂一点，但是无论如何这都是递归的。

绵扇寸访

将其作为单独的答案发布，因为这会占用一些空间。这是递归调用的表示。为了节省空间，我将left更改为lo，将right更改为hi，将pivot更改为piv。虽然连接可能很难遵循，但是它很好地显示了流程。

                          qsort( [7,3,28,8,9,13,1500,45] )
                                           |
             |-----------------------------v-----------------------------------|
             | lo=[3]                   piv=7           hi=[28,8,9,13,1500,45] |
                 |                                                  |
                 |                                                  |
                 v                                                  v
            qsort( [3] )                             qsort( [28,8,9,13,1500,45] )
                 |                                                  |
   |-------------v------------|       |-----------------------------v--------------------------------------------|
   | lo=[]    piv=3     hi=[] |       | lo=[8,9,13]               piv=28                            hi=[1500,45] |
       |                 |                   |                                                              |
       |                 |                   |                                                              |
       v                 v                   v                                                              v
  qsort( [] )       qsort( [] )       qsort( [8,9,13] )                                           qsort( [1500,45] )
                                             |                                                              |
                                |------------v---------------|                                |-------------v--------------|
                                | lo=[]   piv=8    hi=[9,13] |                                | lo=[45]   piv=1500   hi=[] |
                                    |                  |                                            |                  |
                                    |                  |                                            |                  |
                                    v                  v                                            v                  v
                                qsort( [] )      qsort( [9,13] )                              qsort( [45] )       qsort( [] )
                                                       |                                            |  
                                         |-------------v -----------|                  |------------v-------------|
                                         | lo=[]    piv=9   hi=[13] |                  | lo=[]    piv=45    hi=[] |
                                            |                  |                           |                  |
                                            |                  |                           |                  |
                                            v                  v                           v                  v
                                       qsort( [] )        qsort( [13] )                qsort( [] )         qsort( [] )
                                                               |           
                                                   |-----------v-------------|
                                                   | lo=[]   piv=13    hi=[] |          
                                                       |                 |          
                                                       |                 |    
                                                       v                 v   
                                                  qsort( [] )        qsort( [] )

要进行串联，基本上是从根开始，尽可能远地深入the35，直到无法深入为止。然后回溯，记下您最近通过的piv，并按照其hi分支以及您可以做的所有lo分支。重复此过程，始终偏爱lo分支，并在回溯时通过piv。这将为您提供完全排序的数组。

辅奈

这将导致递归停止

if (a.length == 0) return [];

珊畴炮贩号

那就是ѭ1线。将空数组传递给函数后，递归停止。由于每个递归的输入数组都被二除，所以这必然发生。底层示例： +是串联 [\"a\",\"b\",\"c\"]最终成为 [] + [a] + [] + [b] + [] + [c] + [] b是枢轴，而a（左）和c（右）都经过另一个快速排序迭代。这会在两者的每一边加一个“ 52”，然后将所有三个连接在一起。

要回复问题请先登录或注册

在这种情况下递归如何工作？

7 个回复

发起人

algorithm

quicksort

javascript

recursion

问题状态

在这种情况下递归如何工作？

与内容相关的链接

7 个回复

发起人

algorithm

quicksort

javascript

recursion

问题状态