递归排序函数

Question

我有一个函数，它根据一组键对一组对象进行排序。这些键具有优先级，sortKey和布尔值来判断它是升序还是降序。我遇到的问题是当你有重复的条目，只有一个键它会抛出一个错误，它会调用index + 1的递归函数，但没有其他键，因此键是未定义的。

这是失败的测试：

it('Should sort with one priority and duplicate entries', () => {
    const arr = [{letter: 'a'}, {letter: 'b'}, {letter: 'a'}];
    const keys: ISortPriority<any>[] = [{sortKey: 'letter', priority: 1, ascending: true}];
    expect(sortObjectsByKey(arr, keys)).toEqual([{letter: 'a'}, {letter: 'a'}, {letter: 'b'}]);
});

以下是我用于排序的代码：

   export function sortObjectsByKey<T>(arrayToSort: T[], sortByKeys: ISortPriority<T>[]): T[] {
       return arrayToSort.sort((a, b) => {
           return sortWithKey(a, b, sortByKeys, 0);
       });
   }

   function sortWithKey<T>(a: T, b: T, keys: ISortPriority<T>[], index: number) {
       keys = keys.sort((c, d) => (c.priority > d.priority) ? 1 : -1);
       const currKey = keys[index].sortKey;
       if (keys[index].ascending) {
           return a[currKey] > b[currKey]
               ? 1
               : (
                   a[currKey] < b[currKey]
                       ? -1
                       : sortWithKey(a, b, keys, index + 1)
               );
       }
       return a[currKey] < b[currKey]
           ? 1
           : (
               a[currKey] > b[currKey]
                   ? -1
                   : sortWithKey(a, b, keys, index + 1)
           );

    }

我试过添加另一个这样的条件：

 return a[currKey] > b[currKey] ? 1 : (a[currKey] < b[currKey] ? -1 : a[currKey] === b[currKey] ? 0 : sortWithKey(a, b, keys, index + 1));

但它会导致其他测试失败。

Answer 1

如果在尝试index < keys.length - 1之前在sortKeys的数量上添加测试（sortWithKey(a, b, keys, index + 1)），则代码正常工作。

更正了下面的实现（在es6中）和使用2个键的测试：

// emulates jest's it
function it(description, test) {
    console.log(description);
    test();
}
// test function
function equals(v1, v2) {
    if (v1 == null && v2 == null) {
        return true;
    }
    if (v1 == null || v2 == null) {
        return false;
    }
    if (typeof v1 !== typeof v2) {
        console.log('fail because', v1, ' and ', v2, 'are not of the same type');
        return false;
    }
    if (typeof v1 === 'object') {
        if (Array.isArray(v1)) {
            // eslint-disable-next-line no-use-before-define
            const res = arrayEquals(v1, v2);
            if (!res) {
              console.log('fail because', v1, '!==', v2);
            }
            return res;
        }
        // eslint-disable-next-line no-use-before-define
        return objectEquals(v1, v2);
    }
    const res = v1 === v2;
    if (!res) {
      console.log('fail because', v1, '!==', v2);
    }
    return res;
}
// test function
function arrayEquals(array1, array2) {
    if (array1.length !== array2.length) {
      console.log('fail because array1 and array2 do not have the same length');
      return false;
    }
    for (let i = 0; i < array1.length; i += 1) {
        if (!equals(array1[i], array2[i])) {
            console.log('fail because', array1[i], '!==', array2[i]);
            return false;
        }
    }
    return true;
}
// test function
function objectEquals(obj1, obj2) {
    const keys1 = Object.keys(obj1);
    if (keys1.length !== Object.keys(obj2).length) {
        console.log('fail because array1 and array2 do not have the same number of keys');
        return false;
    }
    for (let i = 0; i < keys1.length; i += 1) {
        const key = keys1[i];
        if (!equals(obj1[key], obj2[key])) {
            console.log('fail because', obj1[key], '!==', obj2[key]);
            return false;
        }
    }
    return true;
}
// emulates jest's expect
function expect(t) {
    return {
        toEqual: (v) => {
            const res = equals(t, v);
            if (res) {
                console.log(`expect ${JSON.stringify(t)} to equals ${JSON.stringify(v)}: Success`);
            } else {
                console.log(`expect ${JSON.stringify(t)} to equals ${JSON.stringify(v)}: Fail`);
            }
        }
    };
}

function sortWithKey(a, b, keys, index) {
    // eslint-disable-next-line no-param-reassign
    keys = keys.sort((c, d) => (c.priority > d.priority ? 1 : -1));
    const currKey = keys[index].sortKey;
    if (keys[index].ascending) {
        return a[currKey] > b[currKey]
            ? 1 :
            (
                a[currKey] < b[currKey]
                    ? -1
                    : (
                        index < keys.length - 1
                            ? sortWithKey(a, b, keys, index + 1)
                            : 0
                    )
            );
    }
    return a[currKey] < b[currKey]
        ? 1
        : (
            a[currKey] > b[currKey]
                ? -1
                : (
                    index < keys.length - 1
                        ? sortWithKey(a, b, keys, index + 1)
                        : 0
                )
        );
}

function sortObjectsByKey(arrayToSort, sortByKeys) {
    return arrayToSort.sort((a, b) => sortWithKey(a, b, sortByKeys, 0));
}

it('Should sort with two priorities and duplicate entries', () => {
    const arr = [{ letter: 'a', n: 1 }, { letter: 'b', n: 1 }, { letter: 'c', n: 0 }, { letter: 'b', n: 0 }, { letter: 'a', n: 0 }];
    const keys = [{ sortKey: 'letter', priority: 1, ascending: false }, {sortKey: 'n', priority: 2, ascending: true}];
    expect(sortObjectsByKey(arr, keys)).toEqual([{"letter":"c","n":0},{"letter":"b","n":0},{"letter":"b","n":1},{"letter":"a","n":0},{"letter":"a","n":1}]);
});

正如其他人所说的那样，它缺乏gard条件，并且在每次递归调用时重新排序键是有点滥用，但你应该从那里开始工作。