如果在逐个插入元素时保持向量列表排序,则基本上执行插入排序,理论上在最坏的情况下运行O(n ^ 2).平均情况也是二次的,这使得插入排序对于排序大型数组是不切实际的.
输入~30000后,最好采用所有输入,然后使用更快的排序算法对其进行排序.
编辑: 正如@Veritas指出的那样,我们可以使用更快的算法来搜索元素的位置(如二进制搜索).所以整个过程需要O(nlg(n))时间.但是,也可以指出,这里插入元素也是要考虑的因素.如果我们想要保持数组排序,那么插入元素的最坏情况需要O(n ^ 2)仍然是整体运行时间.
输入之后的排序仍然是更好的方法,而不是在每次迭代后保持排序.