任何人都可以解释为什么插入排序的时间复杂度为Θ（n²）？
我很确定我将时间复杂性理解为一个概念，但我并不真正理解如何将它应用于这种排序算法。我应该只看数学证据来找到这个答案吗？
平均每个插入必须遍历当前排序列表的一半，同时每步进行一次比较。该列表每次增长一个。
因此，从长度为1的列表开始并插入第一个项目以获得长度为2的列表，我们平均遍历.5（0或1）个位置。其余为1.5（0,1或2位），2.5,3.5，...，n-.5，长度为n + 1的列表。
这是通过简单代数，1 + 2 + 3 + ... + n - n * .5 =（n（n + 1） - n）/ 2 = n ^ 2/2 = O（n ^ 2）
请注意，这是一般情况。在最坏的情况下，列表必须完全遍历（您始终将下一个最小的项插入升序列表）。然后你有1 + 2 + ... n，它仍然是O（n ^ 2）。
在最好的情况下，您会在顶部元素处找到具有一个比较的插入点，因此您有1 + 1 + 1 +（n次）= O（n）。
它仅适用于数组/列表 - 即插入/删除时间为O（n）的结构。它可能与其他数据结构不同。例如，对于跳过列表，它将是O（n * log（n）），因为跳过列表中的O（log（n））中可以进行二进制搜索，但插入/删除将是常量。
插入排序算法的最坏情况时间复杂度为O（n ^ 2）。最糟糕的插入排序是当数组中的元素已经按递减顺序存储并且您希望按递增顺序对数组进行排序时。
假设你有一个数组
Step 1 => | 4 | 3 | 2 | 1 | No. of comparisons = 1 | No. of movements = 1
Step 2 => | 3 | 4 | 2 | 1 | No. of comparisons = 2 | No. of movements = 2
Step 3 => | 2 | 3 | 4 | 1 | No. of comparisons = 3 | No. of movements = 3
Step 4 => | 1 | 2 | 3 | 4 | No. of comparisons = 4 | No. of movements = 4
T（n）= 2 + 4 + 6 + 8 + ---------- + 2（n-1）
T（n）= 2 *（1 + 2 + 3 + 4 + -------- +（n-1））
T（n）= 2 *（n（n-1））/ 2
T（n）= O（n ^ 2）