12.4日记-526互联

假设数组的长度为 n，现在，如果需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来，给新来的数据，需要将第 k～n 这部分的元素都顺序地往后挪一位。那插入操作的时间复杂度是多少呢？

如果在数组的末尾插入元素，那就不需要移动数据了，这时的时间复杂度为 O ( 1 ) O(1) O(1)。但如果在数组的开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是 O ( n ) O(n) O(n)。因为在每个位置插入元素的概率是一样的，所以平均情况时间复杂度为 1 + 2 + … n n = O ( n ) {1 + 2 + … n \over n} = O(n) n1+2+…n=O(n)

如果数组中的数据是有序的，在某个位置插入一个新的元素时，就必须按照刚才的方法搬移 k 之后的数据。但是，如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。在这种情况下，如果要将某个数组插入到第 k 个位置，为了避免大规模的数据搬移，还有一个简单的办法就是，直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置

例如数组 a[10] 中存储了如下 5 个元素：a，b，c，d，e。现在需要将元素 x 插入到第 3 个位置。只需要将 c 放入到 a[5]，将 a[2] 赋值为 x 即可。最后，数组中的元素如下： a，b，x，d，e，c

利用这种处理技巧，在特定场景下，在第 k 个位置插入一个元素的时间复杂度就会降为 O ( 1 ) O(1) O(1)。这个处理思想在快排中也会用到