修改合并排序以在 JavaScript 中计算反转

modifying mergesort to count inversions in JavaScript

本文关键字：计算 JavaScript 合并 排序 修改      更新时间：2023-09-26

我的问题有没有更好的方法来优化下面的代码？ 每次合并数组时，inversions都会重置并递增，并且在 2 个排序数组（左半部分和右半部分）的最终合并中，我们得到 inversions 的最终值。有没有更好/更清洁的做事方式没有全局变量？谢谢！

var inversions = 0;
  function mergeSortedArray(a, b){
    var merged = [], 
        aElm = a[0],
        bElm = b[0],
        i = 1,
        j = 1,
        inversions = 0;
    while(aElm || bElm){
     if((aElm && !bElm) || aElm < bElm){
       merged.push(aElm);
       aElm = a[i++];
     }   
     else {
       merged.push(bElm);
       bElm = b[j++];
       inversions++;
     }
    }
    return merged;
  }
  function mergeSort(items){

      if (items.length < 2) {
          return items;
      }
      var middle = Math.floor(items.length / 2),
          left    = items.slice(0, middle),
          right   = items.slice(middle);
      return mergeSortedArray(mergeSort(left), mergeSort(right));
  }

优化往往是丑陋的。

我看到的主要性能问题是有很多创建数据被作为垃圾丢弃。 要解决这个问题，你可以做的是有一个输入数组和一个输出数组。 您将两个数组以及两个块要合并的位置的索引传递给合并函数。 返回反转次数。 在合并排序的每个级别，输入数组和输出数组的角色都会交换。

代码将很挑剔、棘手且难以阅读。 但应该表现得更好。

至于全局，在代码中处理它的"理论上正确"的方法是返回一个同时包含数组和计数的数据结构。 然而，下一个最好的（在我看来是首选的）方法是在通过全局通信的函数周围放置一个块。 在 mergeSort 中初始化它，在 mergeSortedArray 中使用它并将该例程重命名为 _mergeSortedArray 以指示它是私有的，不应调用。 这将保持可读性，同时保证正确使用现在更好的本地化全局。

相关文章：