递归选择排序（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. 您必须添加完成递归的条件（所谓的Base case）if ( !arr.length ) return []
2. arr.splice( findSmallestIndex( arr ), 1 )返回 Array 并且不需要 in [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. 掌握递归编程
2. Array.prototype.splice()
3. 基本情况- 可以非递归地陈述解决方案的情况
4. 一般（递归）情况 - 解决方案以其自身的较小版本表示的情况