假设我已经有一个包含这些文章的数组，按从低到高的价格排序：
[
{ 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);
如果列表很长，则不希望每次都对列表进行排序。带有浮点数的排序充其量是 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)。二叉搜索非常简单。你从中间开始。如果元素大于要搜索的元素，请将相同的算法应用于列表的上半部分，否则应用于下半部分。在 Web 上很容易找到二叉搜索的代码示例。
下面是一个示例：
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. 时间以毫秒为单位。请注意，基准测试非常原始，但它给出了当大小增长时它的影响程度的想法。
为了避免每次对数组进行排序，您可以遍历数组，直到找到价格更高的元素，然后使用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)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);
我在 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;
}
要使用此功能，您必须在 .
usage 示例中导入此文件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);
这是我当前的打字稿实现：
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);
只需推送您的项目
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);
});
考虑我的解决方案如下;
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');
不确定这是否是最佳的，但您可以将其推送到另一个(重复的)数组中，然后对其进行排序，然后检查其索引以将其推送到正确的索引位置：
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);