将数字插入排序的数字数组的有效方法？

插入函数假定给定数组已排序，它直接搜索可以插入新元素的位置，通常只需查看数组中的几个元素。

数组的一般排序函数不能采用这些快捷方式。显然，它至少必须检查数组中的所有元素，看看它们是否已经正确排序。仅这一事实就使常规排序比插入函数慢。

通用排序算法通常平均为 O（n ⋅ log（n）），并且根据实现的不同，如果数组已经排序，它实际上可能是最坏的情况，从而导致 O（n²） 的复杂性。相反，直接搜索插入位置的复杂度仅为 O（log（n）），因此它总是要快得多。

以下是一些想法： 首先，如果你真的关心代码的运行时，一定要知道当你调用内置函数时会发生什么！我不知道 javascript 中的上下关系，但是快速搜索拼接函数返回了这一点，这似乎表明您每次调用都会创建一个全新的数组！我不知道这是否真的重要，但它肯定与效率有关。我看到 Breton 在评论中已经指出了这一点，但它肯定适用于您选择的任何数组操作函数。

无论如何，要真正解决问题。

当我读到你想排序时，我的第一个想法是使用插入排序！。它很方便，因为它在排序或接近排序的列表上以线性时间运行。由于您的数组将只有 1 个元素不按顺序排列，因此这算作近似排序的元素（除了大小为 2 或 3 或其他大小的数组，但此时，c'mon）。现在，实现排序还不错，但这是一个你可能不想处理的麻烦，而且，我对 javascript 一无所知，也不知道它是否容易或困难或其他什么。这消除了对查找函数的需求，您只需推送（正如 Breton 建议的那样）。

其次，您的“快速排序式”查找函数似乎是一种二叉搜索算法！这是一个非常好的算法，直观且快速，但有一个问题：众所周知，它很难正确实现。我不敢说你的是否正确（我希望它是，当然！:)），但如果你想使用它，请小心。

无论如何，总结：使用带有插入排序的“推送”将在线性时间内工作（假设数组的其余部分已排序），并避免任何混乱的二叉搜索算法要求。我不知道这是否是最好的方法（数组的底层实现，也许一个疯狂的内置函数做得更好，谁知道呢），但这对我来说似乎是合理的。:) - 阿戈尔。

就像一个数据点一样，对于踢球，我测试了这一点，在Windows 7上使用Chrome的两种方法将1000个随机元素插入到100,000个预排序数字的数组中：

First Method:
~54 milliseconds
Second Method:
~57 seconds

因此，至少在这种设置中，本机方法并不能弥补它。即使对于小型数据集也是如此，将 100 个元素插入到 1000 个数组中：

First Method:
1 milliseconds
Second Method:
34 milliseconds

不要在每件物品之后重新排序，这太过分了。

如果只有一个项目要插入，则可以使用二进制搜索找到要插入的位置。然后使用 memcpy 或类似工具批量复制剩余的项目，为插入的项目腾出空间。二进制搜索是 O（log n），副本是 O（n），总计为 O（n + log n）。使用上述方法，您将在每次插入后进行重新排序，即 O（n log n）。

这有关系吗？假设您随机插入 k 个元素，其中 k = 1000。排序列表为 5000 个项目。

• Binary search + Move = k*(n + log n) = 1000*(5000 + 12) = 5,000,012 = ~5 million ops
• Re-sort on each = k*(n log n) = ~60 million ops

如果要插入的 k 个项目随时到达，则必须执行 search+move。但是，如果提前给你一个要插入到排序数组中的 k 个项目的列表，那么你可以做得更好。对 k 个项目进行排序，与已排序的 n 个数组分开。然后进行扫描排序，同时向下移动两个排序的数组，将一个数组合并到另一个数组中。 - 一步合并排序 = k log k + n = 9965 + 5000 = ~15,000 ops

更新：关于您的问题。
。 准确地解释了你得到的时间。First method = binary search+move = O(n + log n)Second method = re-sort = O(n log n)

您的代码中存在一个错误。它应该写成：

function locationOf(element, array, start, end) {
  start = start || 0;
  end = end || array.length;
  var pivot = parseInt(start + (end - start) / 2, 10);
  if (array[pivot] === element) return pivot;
  if (end - start <= 1)
    return array[pivot] > element ? pivot - 1 : pivot;
  if (array[pivot] < element) {
    return locationOf(element, array, pivot, end);
  } else {
    return locationOf(element, array, start, pivot);
  }
}

如果没有此修复，代码将永远无法在数组的开头插入元素。

非常好和非凡的问题，有一个非常有趣的讨论！在推送包含数千个对象的数组中的单个元素后，我也使用了该函数。Array.sort()

为了我的目的，我不得不扩展您的函数，因为有复杂的对象，因此需要一个比较函数，如：locationOfArray.sort()

function locationOf(element, array, comparer, start, end) {
    if (array.length === 0)
        return -1;

    start = start || 0;
    end = end || array.length;
    var pivot = (start + end) >> 1;  // should be faster than dividing by 2

    var c = comparer(element, array[pivot]);
    if (end - start <= 1) return c == -1 ? pivot - 1 : pivot;

    switch (c) {
        case -1: return locationOf(element, array, comparer, start, pivot);
        case 0: return pivot;
        case 1: return locationOf(element, array, comparer, pivot, end);
    };
};

// sample for objects like {lastName: 'Miller', ...}
var patientCompare = function (a, b) {
    if (a.lastName < b.lastName) return -1;
    if (a.lastName > b.lastName) return 1;
    return 0;
};

简单（演示）：

function sortedIndex(array, value) {
    var low = 0,
        high = array.length;

    while (low < high) {
        var mid = (low + high) >>> 1;
        if (array[mid] < value) low = mid + 1;
        else high = mid;
    }
    return low;
}

对于少数项目，差异是微不足道的。但是，如果您要插入大量项目，或者使用非常大的数组，则在每次插入后调用 .sort（） 将导致大量开销。

我最终为此目的编写了一个非常巧妙的二进制搜索/插入函数，所以我想我会分享它。由于它使用循环而不是递归，因此不会对额外的函数调用进行偷听，因此我认为性能将比最初发布的任何一种方法都要好。默认情况下，它模拟默认比较器，但如果需要，可以接受自定义比较器功能。whileArray.sort()

function insertSorted(arr, item, comparator) {
    if (comparator == null) {
        // emulate the default Array.sort() comparator
        comparator = function(a, b) {
            if (typeof a !== 'string') a = String(a);
            if (typeof b !== 'string') b = String(b);
            return (a > b ? 1 : (a < b ? -1 : 0));
        };
    }

    // get the index we need to insert the item at
    var min = 0;
    var max = arr.length;
    var index = Math.floor((min + max) / 2);
    while (max > min) {
        if (comparator(item, arr[index]) < 0) {
            max = index;
        } else {
            min = index + 1;
        }
        index = Math.floor((min + max) / 2);
    }

    // insert the item
    arr.splice(index, 0, item);
};

如果您愿意使用其他库，lodash 提供了 sortedIndex 和 sortedLastIndex 函数，它们可以用来代替循环。两个潜在的缺点是 1） 性能不如我的方法好（以为我不确定它有多差）和 2） 它不接受自定义比较器函数，只接受获取要比较的值的方法（使用默认比较器，我假设）。while

我知道这是一个已经有答案的老问题，还有很多其他不错的答案。我看到一些答案表明，您可以通过在 O（log n） 中查找正确的插入索引来解决这个问题 - 您可以，但您不能在那个时候插入，因为数组需要部分复制以腾出空间。

底线：如果你真的需要 O（log n） 在排序数组中插入和删除，你需要一个不同的数据结构 - 而不是一个数组。您应该使用 B 树。将 B 树用于大型数据集将获得的性能提升将使此处提供的任何改进相形见绌。

如果必须使用数组。我提供了以下基于插入排序的代码，当且仅当数组已经排序时，该代码才有效。这对于每次插入后都需要求助的情况很有用：

function addAndSort(arr, val) {
    arr.push(val);
    for (i = arr.length - 1; i > 0 && arr[i] < arr[i-1]; i--) {
        var tmp = arr[i];
        arr[i] = arr[i-1];
        arr[i-1] = tmp;
    }
    return arr;
}

它应该在 O（n） 中运行，我认为这是你能做的最好的。如果 js 支持多次分配，那就更好了。下面是一个可以玩的例子：

更新：

这可能更快：

function addAndSort2(arr, val) {
    arr.push(val);
    i = arr.length - 1;
    item = arr[i];
    while (i > 0 && item < arr[i-1]) {
        arr[i] = arr[i-1];
        i -= 1;
    }
    arr[i] = item;
    return arr;
}

更新 2

@terrymorse在评论中指出，javascripts Array.splice 方法的速度非常快，而且它不仅仅是在时间复杂度上的不断改进。似乎正在使用一些链表魔术。这意味着您仍然需要与普通数组不同的数据结构 - 只是 javascript 数组可能会在本机提供不同的数据结构。

更新了 JS Bin 链接

function insertOrdered(array, elem) {
    let _array = array;
    let i = 0;
    while ( i < array.length && array[i] < elem ) {i ++};
    _array.splice(i, 0, elem);
    return _array;
}

以下是用于实现此目的的四种不同算法的比较： https://jsperf.com/sorted-array-insert-comparison/1

算法

• 幼稚：之后只需推送和排序（）
• 线性：遍历数组并在适当的情况下插入
• 二进制搜索：取自 https://stackoverflow.com/a/20352387/154329
• “Quick Sort Like”：来自 syntheticzero （https://stackoverflow.com/a/18341744/154329 的精炼解决方案)

天真总是可怕的。对于较小的数组大小，其他三个似乎没有太大区别，但对于较大的数组，最后两个优于简单的线性方法。

这是一个使用 lodash 的版本。

const _ = require('lodash');
sortedArr.splice(_.sortedIndex(sortedArr,valueToInsert) ,0,valueToInsert);

注意：sortedIndex 执行二进制搜索。

我能想到的最好的数据结构是索引跳过列表，它维护链表的插入属性，并具有支持日志时间操作的层次结构。平均而言，搜索、插入和随机访问查找可以在 O（log n） 时间内完成。

顺序统计树支持使用秩函数对日志时间进行索引。

如果你不需要随机访问，但你需要O（log n）插入和搜索键，你可以放弃数组结构，使用任何类型的二叉搜索树。

没有一个答案是有效的，因为这是平均 O（n） 时间。谷歌浏览器中array.splice（）的时间复杂度是多少？array.splice()

这是我的函数，使用二进制搜索来查找项目，然后适当地插入：

function binaryInsert(val, arr){
    let mid, 
    len=arr.length,
    start=0,
    end=len-1;
    while(start <= end){
        mid = Math.floor((end + start)/2);
        if(val <= arr[mid]){
            if(val >= arr[mid-1]){
                arr.splice(mid,0,val);
                break;
            }
            end = mid-1;
        }else{
            if(val <= arr[mid+1]){
                arr.splice(mid+1,0,val);
                break;
            }
            start = mid+1;
        }
    }
    return arr;
}

console.log(binaryInsert(16, [
    5,   6,  14,  19, 23, 44,
   35,  51,  86,  68, 63, 71,
   87, 117
 ]));

带有自定义比较方法的 TypeScript 版本：

const { compare } = new Intl.Collator(undefined, {
  numeric: true,
  sensitivity: "base"
});

const insert = (items: string[], item: string) => {
    let low = 0;
    let high = items.length;

    while (low < high) {
        const mid = (low + high) >> 1;
        compare(items[mid], item) > 0
            ? (high = mid)
            : (low = mid + 1);
    }

    items.splice(low, 0, item);
};

用：

const items = [];

insert(items, "item 12");
insert(items, "item 1");
insert(items, "item 2");
insert(items, "item 22");

console.log(items);

// ["item 1", "item 2", "item 12", "item 22"]

如果你的第一个代码没有错误，我最好的猜测是，这将是你在 JS 中完成这项工作的方式。我的意思是;

1. 进行二进制搜索以查找插入索引
2. 用于执行插入。splice

这几乎总是比自上而下或自下而上的线性搜索和插入快 2 倍，正如 domoarigato 的答案中提到的，我非常喜欢它，并将其作为我的基准测试的基础，最后和 .pushsort

当然，在许多情况下，您可能正在现实生活中的某些对象上执行这项工作，在这里，我为这三种情况生成了一个基准测试，用于容纳一些对象的大小为 100000 的数组。随意玩它。

function insertElementToSorted(arr, ele, start=0,end=null) {
    var n , mid
    
    if (end == null) {
        end = arr.length-1;
    }
    n = end - start 
     
    if (n%2 == 0) {
        mid = start + n/2;        
    } else {
      mid = start + (n-1)/2
    }
    if (start == end) {
        return start
    }
 

    if (arr[0] > ele ) return 0;
    if (arr[end] < ele) return end+2; 
    if (arr[mid] >= ele  &&   arr[mid-1] <= ele) {
        return mid
    }

    if (arr[mid] > ele  &&   arr[mid-1] > ele) {
        return insertElementToSorted(arr,ele,start,mid-1)    
    }

    if (arr[mid] <= ele  &&   arr[mid+1] >= ele) {
        return  mid + 1
    }

    if (arr[mid] < ele  &&   arr[mid-1] < ele) {
        return insertElementToSorted(arr,ele,mid,end)
    }

    if(arr[mid] < ele  &&   arr[mid+1] < ele) {
           console.log("mid+1", mid+1, end)
          return insertElementToSorted(arr,ele,mid+1,end)
    
    }
}

// Example

var test = [1,2,5,9, 10, 14, 17,21, 35, 38,54, 78, 89,102];
insertElementToSorted(test,6)

作为对我未来自我的备忘录，这是另一个版本，针对极端情况进行了一些优化，并进行了初步测试。findOrAddSorted

// returns BigInt(index) if the item has been found
// or BigInt(index) + BigInt(MAX_SAFE_INTEGER) if it has been inserted 
function findOrAddSorted(items, newItem) {
  let from = 0;
  let to = items.length;
  let item;

  // check if the array is empty
  if (to === 0) {
    items.push(newItem);
    return BigInt(Number.MAX_SAFE_INTEGER);
  }

  // compare with the first item
  item = items[0];
  if (newItem === item) {
    return 0;
  }
  if (newItem < item) {
    items.splice(0, 0, newItem);
    return BigInt(Number.MAX_SAFE_INTEGER);
  }

  // compare with the last item
  item = items[to-1];
  if (newItem === item) {
    return BigInt(to-1);
  }
  if (newItem > item) {
    items.push(newItem);
    return BigInt(to) + BigInt(Number.MAX_SAFE_INTEGER);
  }

  // binary search
  let where;
  for (;;) {
    where = (from + to) >> 1;
    if (from >= to) {
      break;
    }

    item = items[where];
    if (item === newItem) {
      return BigInt(where);
    }
    if (item < newItem) {
      from = where + 1;
    }
    else {
      to = where;
    }
  }

  // insert newItem
  items.splice(where, 0, newItem);
  return BigInt(where) + BigInt(Number.MAX_SAFE_INTEGER);
}

// generate a random integer < MAX_SAFE_INTEGER
const generateRandomInt = () => Math.floor(Math.random() * Number.MAX_SAFE_INTEGER);

// fill the array with random numbers
const items = new Array();
const amount = 1000;
let i = 0;
let where = 0;
for (i = 0; i < amount; i++) {
  where = findOrAddSorted(items, generateRandomInt());
  if (where < BigInt(Number.MAX_SAFE_INTEGER)) {
    break;
  }
}

if (where < BigInt(Number.MAX_SAFE_INTEGER)) {
  console.log(`items: ${i}, repeated at ${where}: ${items[Number(where)]}`)
}
else {
  const at = Number(where - BigInt(Number.MAX_SAFE_INTEGER));
  console.log(`items: ${i}, last insert at: ${at}: ${items[at]}`);
}
console.log(items);