如何将一个元素推入一个已排序的数组中指定的位置？

Question

如何将一个元素推入一个已排序的数组中指定的位置？

18

假设我已经有一个数组，其中包含这些商品，并按价格从低到高排序:

[
  { title: "Article 3", price: 1.49 },
  { title: "Article 1", price: 3.00 },
  { title: "Article 4", price: 5.99 },
  { title: "Article 2", price: 19.99 }
]

基本上我想将另一篇文章按正确的位置（根据价格）插入到数组中。我该如何做呢？

我要插入的新文章可能具有以下属性：

{ title: "Article 5", price: 12.00 }

我希望这篇文章出现在索引3处（在文章4和2之间）。

更新（解决方案）

我使用@klutt的答案创建了一个原型方法，其中包含二分搜索算法：

Array.prototype.pushSorted = function(el, compareFn) {
  this.splice((function(arr) {
    var m = 0;
    var n = arr.length - 1;

    while(m <= n) {
      var k = (n + m) >> 1;
      var cmp = compareFn(el, arr[k]);

      if(cmp > 0) m = k + 1;
        else if(cmp < 0) n = k - 1;
        else return k;
    }

    return -m - 1;
  })(this), 0, el);

  return this.length;
};

const sortByPrice = (a, b) => a.price > b.price;
theArray.pushSorted({ title: "Article 5", price: 12.00 }, sortByPrice);

- Nordling Art

“without knowing current elements”这句话的意思有点不太清楚。我猜你可以访问列表，对吗？那么你可以读取它吗？ - klutt

@NordlingArt 不用担心，但请将该部分从问题中删除，以便日后的读者。 - klutt

2

@NordlingArt FYI，splice函数无法在需要时将元素插入到数组的最后一个位置。应该返回m而不是-m-1吗？ - Vincent

1

@NordlingArt 这个原型解决方案不起作用！使用一个简单的整数列表，我得到了一个非常不排序的数组。仍在努力找出问题所在... - jpro

这里的解决方案对我不起作用，但是这个问题的另一个答案可以：https://dev59.com/CFgQ5IYBdhLWcg3wUiZS#56588334 - Peter

显示剩余9条评论

8个回答

3

为避免每次排序数组，您可以遍历数组直到找到价格更高的元素，然后使用array.splice(index, 0, element)将您的元素插入正确的位置：

var array = [
  { title: "Article 3", price: 1.49 },
  { title: "Article 1", price: 3.00 },
  { title: "Article 4", price: 5.99 },
  { title: "Article 2", price: 19.99 }
]

function insertSorted (array, element, comparator) {
  for (var i = 0; i < array.length && comparator(array[i], element) < 0; i++) {}
  array.splice(i, 0, element)
}

function compareByPrice (a, b) { return a.price - b.price }

insertSorted(array, { title: "Article 5", price: 12.00 }, compareByPrice)

console.log(array)

- gyre

2

< p >“Update (Solution)”仍然不太好用。应该放在开头或结尾的项目会被放在错误的位置，请参考基于相同代码的修订解决方案：

最初的回答

Array.prototype.pushSorted = function(el, compareFn) {
  let index = (function(arr) {
    var m = 0;
    var n = arr.length - 1;

    while(m <= n) {
      var k = (n + m) >> 1;
      var cmp = compareFn(el, arr[k]);

      if(cmp > 0) m = k + 1;
        else if(cmp < 0) n = k - 1;
        else {
          console.log(`m=${m} k=${k}`)
          return k;
        };
    }


    return -m - 1;
  })(this);

  if (index >= 0)
    this.splice(index, 0, el);
  else if (index < 0)
    this.splice((index * -1) - 1, 0, el);

  return this.length;
};

最初的回答：

使用示例：

a = [1, 2, 3, 4, 5]
a.pushSorted(2.5, (a,b) => a - b);
a.pushSorted(8, (a,b) => a - b);
a.pushSorted(0.5, (a,b) => a - b);

- Pablote

这段代码似乎仍然无法正常工作。以下是输出结果： [1, 2, 8, 0.5, 2.5, 3, 4, 5] - Lakshmikant Deshpande

可以，但你确定没有在测试另一个实现吗？ - Pablote

1

似乎对我有效。 - Peter

1

这是我的当前TypeScript实现：

enum SortDirection {
  Ascending,
  Descending
}

const propertyComparer = <T>(
  a: T,
  b: T,
  property: keyof T,
  direction: SortDirection
): number => {
  if (a[property] < b[property]) {
    return direction === SortDirection.Ascending ? 1 : -1;
  }
  if (a[property] > b[property]) {
    return direction === SortDirection.Ascending ? -1 : 1;
  }
  return 0;
};

const findAndInsertByProperty = <T>(
  arr: T[],
  item: T,
  property: keyof T,
  direction: SortDirection
): number => {
  let start = 0;
  let end = arr.length;

  while (start < end) {
    const mid = (start + end) >> 1;
    const result = propertyComparer<T>(item, arr[mid], property, direction);

    if (result === 0) {
      return mid;
    } else if (result < 0) {
      end = mid;
    } else {
      start = mid + 1;
    }
  }

  return end;
};

const myArray = [
  { title: "Article 3", price: 1.49 },
  { title: "Article 1", price: 3.00 },
  { title: "Article 4", price: 5.99 },
  { title: "Article 2", price: 19.99 }
];
const value = { title: "Article 5", price: 12.00 };
const valueLowest = { title: "Article 6", price: 0.49 };
const valueHighest = { title: "Article 7", price: 20.00 };

myArray.splice(findAndInsertByProperty(myArray, value, 'price', SortDirection.Descending), 0, value);
myArray.splice(findAndInsertByProperty(myArray, valueLowest, 'price', SortDirection.Descending), 0, valueLowest);
myArray.splice(findAndInsertByProperty(myArray, valueHighest, 'price', SortDirection.Descending), 0, valueHighest);

console.log(myArray);

- Icehunter

非常好的一个，如果您能编辑您的答案并添加JS版本，我将不胜感激。 - PirateApp

1

我在 Angular 中通过调整代码来实现了这一点。有人可能会发现它很有用。

Array.prototype.sortedInsert = sortedInsert;

interface Array<T> {
    sortedInsert(element: T, comparator: any): number;
}

/**
 *  This function takes an element, and a comparator function.
 *  It returns position of the inserted record.
 */

function sortedInsert<T>(element: T, comparatorFn: any): number {
    const insertionIndex: number = findInsertionIndex(this, element, comparatorFn);
    this.splice(insertionIndex, 0, element);
    return insertionIndex;
}

function findInsertionIndex<T>(arr: Array<T>, element: T, comparatorFn: any): number {
    if (arr.length === 0) {
        return 0;
    }

    let low: number = 0;
    let high: number = arr.length - 1;

    while (low <= high) {
        const mid: number = Math.floor(low + (high - low) / 2);
        const comparison: number = comparatorFn(element, arr[mid]);
        if (comparison === 0) {
            return mid;
        } else if (comparison < 0) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

要使用此功能，您需要在app.module.ts中导入此文件。
使用示例：

const arr = [];
const comp = (a: number, b: number) => a - b;
arr.sortedInsert(2, comp);
arr.sortedInsert(1, comp);
arr.sortedInsert(3, comp);
console.log(arr);

- Lakshmikant Deshpande

0

只需推送您的项目

var myArray = [
  { title: "Article 3", price: 1.49 },
  { title: "Article 1", price: 3.00 },
  { title: "Article 4", price: 5.99 },
  { title: "Article 2", price: 19.99 }
]

myArray.push({ title: "Article 5", price: 12.00 })

对数组进行排序：

myArray.sort(function(a, b) {
    return parseFloat(a.price) - parseFloat(b.price);
});

- Lionel B

1

我要给这个投票点踩，因为它没有利用数组一开始就已经被排序的优势。 - klutt

-1

请参考我的解决方案：

var articles=[
  { title: "Article 3", price: 1.49 },
  { title: "Article 1", price: 3.00 },
  { title: "Article 4", price: 5.99 },
  { title: "Article 2", price: 19.99 }
]

现在按照这种方式编写一个函数；

function sortByKey(array, key) {
    return array.sort(function(a, b) {
        var x = a[key]; var y = b[key];
       return ((x < y) ? -1 : ((x > y) ? 1 : 0));
   });
}

现在插入一个元素；

articles.push({ title: "Article 5", price: 12.00 });

最后进行排序；

articles=sortByKey(articles, 'price');

- KOUSIK MANDAL

2

我会给这个点踩个赞，因为它没有充分利用数组一开始就排序的优势。 - klutt

-2

不确定这是否是最优的方法，但您可以将其推入另一个（重复的）数组中，然后对其进行排序，然后检查其索引以便将其推入正确的索引位置：

Array.prototype.pushSorted = function(value, compareFunction) {
  const arrCopy = this.map(element => element);

  arrCopy.push(value);
  arrCopy.sort(compareFunction);
  this.splice(arrCopy.indexOf(value), 0, value);

  return this.length;
};

首先，我们创建一个数组实例的副本。然后将元素推入此数组副本中。接着对数组副本进行排序。然后通过检查其在数组副本中的索引，使用splice方法将元素推入真正的数组中。最后，我们可以像普通的push一样返回数组长度。

示例：

const sortByPrice = (a, b) => a > b ? 1 : -1;
const newArticle = { title: "Article 5", price: 12.00 };

theArray.pushSorted(newArticle, sortByPrice);

- Nordling Art

我会给这个点踩个赞，因为它没有充分利用数组一开始就是排序好的这个事实。 - klutt

看看我的和gyres的答案，看看有什么问题。如果你知道数组已经排序了，就不需要再排序它了。你只需要搜索正确的位置并插入元素即可。 - klutt

它确实可以工作，但问题中明确说明原始数组已排序。这只是一个关于优化的问题，这是真的。但是既然你说列表已排序，一个好的答案应该利用这一点，特别是在这种情况下甚至不难做到。 - klutt

修改对象的原型不被推荐。 - robertmain

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- klutt · Accepted Answer

如果列表非常长，你不希望每次都对其进行排序。使用浮点数进行排序，最好的复杂度为O(n*log n)。而直接进行线性搜索，则可以达到O(n)的复杂度。

function search(a, v) {
    if(a[0]['price'] > v['price']) {
        return 0;
    }
    var i=1;
    while (i<a.length && !(a[i]['price'] > v['price'] && a[i-1]['price'] <= v['price'])) {
        i=i+1;
        }
    return i;
}

myArray.splice(search(myArray, newItem), 0, newItem)

然而，如果列表非常长，使用二分搜索而不是线性搜索会是一个好主意。这将把时间复杂度降至O(log n)。二分搜索非常简单。你从中间开始。如果元素比你要搜索的大，则对列表的上半部分应用相同的算法，否则对下半部分应用相同算法。在网上很容易找到二分搜索的代码示例。

下面是一个示例：

function binarySearch(ar, el, compare_fn) {
    if (el.price < ar[0].price)
        return 0;
    if (el.price > ar[ar.length-1].price)
        return ar.length;
    var m = 0;
    var n = ar.length - 1;
    while (m <= n) {
        var k = (n + m) >> 1;
        var cmp = compare_fn(el, ar[k]);
        if (cmp > 0) {
            m = k + 1;
        } else if(cmp < 0) {
            n = k - 1;
        } else {
            return k;
        }
    }
    return -m - 1;
}

function comp(a, b) {
    return a['price']>b['price']
}

myArray.splice(binarySearch(myArray, element, comp), 0, element)

(从这里偷来的 JavaScript中的二分查找)

但归纳起来，先添加元素然后排序通常不是一个好主意。最好的情况是它没有影响，但既然你知道列表是已排序的，为什么不至少执行一次线性搜索呢？

如果列表很小，那么这并不重要，但如果列表包含数百万个元素，则差异将非常明显。

编辑:

我进行了一个快速而原始的基准测试。

            10,000   100,000  1000,000   10,000,000  
Sort            80       900     13000          N/A
Linear           2         2        25         5000
Binary           2         2         5           21

我测量了三种算法在四个不同大小上运行所需的时间。我不想等待对一千万个元素进行排序结束，因此是N/A。时间以毫秒为单位。请注意，这些基准测试非常简单，但它们可以让我们大致了解当数据规模增大时性能的影响。