javascript - 为什么这种插入排序无法对对象数组进行排序？ (但可以其他值)

Question

我已经制作了这个插入排序算法，如果您在第二个循环中删除 .name，它可以很好地处理数字/字符串。虽然我不能让它与一组对象一起工作？ (我什至尝试了几次桌面检查，但我仍然无法找出问题所在......)

function insertSortByName(d) {
    const len = d.length - 1;
    let output = d;

    for(let sorted = len; sorted >= 0; sorted--) {

        for(let key = sorted-1; output[key].name > output[key+1].name; key++) {
            output = swapArrayVal(output, key, key+1);
        }

    }

    return output;
}

function swapArrayVal(arr, pos1, pos2) {
    let tempVal = arr[pos1];
    arr[pos1] = arr[pos2];
    arr[pos2] = tempVal;
    return arr;
}

这可以用这样的示例数组运行:

insertSortByName([ {name: 'z'}, {name: 'm'}, {name: 'a'} ]);
/* Should return: [ {name: 'a'}, {name: 'm'}, {name: 'z'}] */

Answer 1

您的问题在这一行:

for(let key = sorted-1; output[key].name > output[key+1].name; key++) {

将其更改为:

for(let key=sorted-1; !!output[key+1] && !!output[key] &&
                            output[key].name>output[key+1].name; key++) {

function insertSortByName(d) {
    const len = d.length - 1;
    let output = d;

    for(let sorted = len; sorted >= 0; sorted--) {

        for(let key = sorted-1; !!output[key+1] && !!output[key] && output[key].name > output[key+1].name; key++) {
            output = swapArrayVal(output, key, key+1);
        }

    }

    return output;
}

function swapArrayVal(arr, pos1, pos2) {
    let tempVal = arr[pos1];
    arr[pos1] = arr[pos2];
    arr[pos2] = tempVal;
    return arr;
}
var retVal = insertSortByName([ {name: 'z'}, {name: 'm'}, {name: 'a'} ]);

console.log(retVal);

不同的实现可以基于可用的算法 wikipedia :

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

在以下代码片段中，我在使用 for 时进行了更改，以创建与您的方法类似的内容:

function insertSortByName(arr) {
    for(var i=1; i<arr.length;) {
        for(var j=i; j>0 && arr[j-1].name > arr[j].name;) {
            var tempVal = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = tempVal;
            j -= 1;
        }
        i += 1;
    }
    return arr;
}
var retVal = insertSortByName([ {name: 'z'}, {name: 'm'}, {name: 'a'} ]);

console.log(retVal);

可以改进之前的代码，添加一个比较回调，例如 sort .通过这种方式，您可以继续对不同的对象使用相同的功能。

function insertSort(arr, compareCallBack) {
    for(var i=1; i<arr.length;) {
        for(var j=i; j>0 && compareCallBack(arr[j-1], arr[j]);) {
            var tempVal = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = tempVal;
            j -= 1;
        }
        i += 1;
    }
    return arr;
}
var retVal = insertSort([ {name: 'z'}, {name: 'm'}, {name: 'a'}, {name: 'b'} ], (a, b) => {return a.name > b.name;});

console.log('insertSort with objects: ' + JSON.stringify(retVal));


retVal = insertSort([ 'z', 'm', 'a', 'b'], (a, b) => {return a.localeCompare(b) > 0;});

console.log('insertSort with letters: ' + retVal);

retVal = insertSort([ 10, 7, 8, 1 ], (a, b) => {return a > b;});

console.log('insertSort with numbers: ' + retVal);