什么是速度快：排序n个元素，或插入n个元素一一在正确的位置？ [英] What is faster: sort n elements, or insert n elements one by one in correct place?

问题描述

一般情况下，什么是更好？插入一些集合N个元素，然后进行排序，或者找出正确的位置插入之前的元素，并在那个地方正好插入（重复N次）

Generally, what is better: insert N elements in some collection and then sort it, or find out the correct place for the element before insert and insert it exactly in that place (repeat N times)?

推荐答案

这是非常依赖所使用的数据结构和应用程序。

It is very dependent on the data structure and application in use.

请注意，在一个的数组中插入一个元素的要求移以下所有内容的权利，从而导致 O（N）插入。
一个二叉搜索树然而，允许插入O（LOGN），但不太缓存高效然后阵列 - 因此速度较慢

Note that inserting an element in an array requires shifting all the following elements to the right, which results in O(n) insertion.
A Binary Search Tree however, allows insertion in O(logn), but is less cache efficient then an array - and thus slower.

在另一方面，插入，然后排序结果高 延迟 插入的最后一个元素之后[该 O（nlogn）排序。
另外 - 如果你要经常查询 - 很少，但添加元素 - 你想避免过于频繁整理 - 守信的元素，以一种简单的方法来实现这一目标。

On the other hand, inserting and then sorting results in high latency after the last element was inserted [The O(nlogn) sort].
Also - if you are going to query very often - but add elements seldom - you want to avoid sorting too often - and keeping elements in order is an easy way to achieve this.

这篇关于什么是速度快：排序n个元素，或插入n个元素一一在正确的位置？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！