javascript - 递归选择排序(JS)

Question

我正在用 JavaScript 编写递归选择排序。

预期行为:我希望函数 selectionSort() 以升序对数组中的值进行排序。

问题:我无法退出递归，我也不知道该怎么做。

错误:

Uncaught RangeError: Maximum call stack size exceeded

---

这是我的代码:

const findSmallestIndex = ( arr ) => {
    let smallest = arr[0];
    let smallestIndex = 0;
    let arrLen = arr.length;

    for ( let i = 0; i < arrLen; i++ ) {
        if ( arr[i] < smallest ) {
            smallest = arr[i];
            smallestIndex = i;
        }
    }
    return smallestIndex;
};

const selectionSort = ( arr ) => {
    let smallest = arr.splice( findSmallestIndex( arr ), 1 );
    return [smallest].concat( selectionSort( arr ) );
};

let arr = [23, 43, 23423, 66, 5, 57, 78, 0, 1];

console.log( selectionSort(arr) );

Answer 1

1. 您必须添加完成递归的条件(所谓的基本情况) if ( !arr.length ) return []
2. arr.splice( findSmallestIndex( arr ), 1 ) 返回 Array 并且不需要 [smallest]... - 只需 smallest.concat( selectionSort ( arr ) )
3. 改进:您的代码改变了 arr(由 ftor 指出)因此我们可以通过添加 let newArray = Array.prototype.slice.call 来修复它( arr );

/**
 * Finds smallest element of an aray
 * @param {Array} arr array for searching
 * @return {number} index of the smallest element in array
 */
const findSmallestIndex = ( arr ) => {
    let smallest = arr[0];
    let smallestIndex = 0;
    let arrLen = arr.length;

    for ( let i = 0; i < arrLen; i++ ) {
        if ( arr[i] < smallest ) {
            smallest = arr[i];
            smallestIndex = i;
        }
    }
    return smallestIndex;
};

/**
 * Sorts recursively an array of numbers
 * @param {Array} arr An array of numbers
 * @return {Array} New sorted array
 */
const selectionSort = ( arr ) => {
    if ( !arr.length ) return [];
    let newArray = Array.prototype.slice.call( arr );
    let smallest = arr.splice( findSmallestIndex( arr ), 1 );
    return smallest.concat( selectionSort( arr ) );
};

let arr = [23, 43, 23423, 66, 5, 57, 78, 0, 1];

console.log( selectionSort(arr) );

精选链接和条款:

1. Mastering recursive programming
2. Array.prototype.splice()
3. Base case - 可以非递归地陈述解决方案的情况
4. General (recursive) case - 根据自身的较小版本表达解决方案的案例