为什么排序比看起来更难

主要观点:

  • 介绍了在 Javascript 中排序数组的相关问题及解决方案,排序仍会带来令人惊喜的 bug,包括默认排序、比较器、传递性等方面的问题。
    关键信息:
  • 默认 Javascript 排序会将混合的字符串和数字按字符串顺序排序,如[10, 2, 'x'].sort()结果为[ 10, 2, 'x' ]
  • 可通过传入比较器函数compareNumbers来修复排序问题,如function compareNumbers(a, b) { return a - b;},但对于字符串仍可能有问题。
  • nativeCompare函数能比较各种类型的值且不返回NaN,但仍可能出现传递性失败的情况,如nativeCompare(2, 'x')等。
  • 要修复排序问题需修复传递性和反对称性,如function typedCompare(a, b) { return nativeCompare(typeof a, typeof b) || nativeCompare(a, b);}
  • Grist 中还有其他排序相关的 bug,如处理空值的比较函数emptyCompareBad存在问题,修复后为function emptyCompareGood(a, b) { return nativeCompare(isEmpty(a), isEmpty(b));}
    重要细节:
  • 现代语言虽有高效排序函数,但理解排序算法能带来满足感,如基于比较的排序算法,其高效是因为最小化比较次数。
  • 比较器的创建需注意支持的类型,错误的比较器会导致数组排序错误,且此问题不限于 Javascript,其他语言如 Python、C++也有类似情况。
阅读 8
0 条评论