按升序插入数组元素与事后排序：时间复杂度孰优？

我们来对比两种数组排序方案的时间复杂度：一种是逐个将元素按升序插入数组，另一种是先按输入顺序填充数组再执行快速排序。以输入4 2 120 -2 3为例，分析哪种方案更优。

方案一：逐个元素有序插入 #

这种方案的思路是每读入一个元素，就找到它在已排序数组中的位置，将后续元素后移，再插入当前元素。对应的C代码实现如下：

int array[n];
int val;
int pl = 0;

pl++;
int aux = 0;
for (int i = 0; i < pl; i++)
{
    if (array[i] > val)
    {
        aux++;
        for (int j = pl; j >= i; j--)
        {
            array[j] = array[j - 1];
            array[i] = val;
            break;
        }
    }
    if (aux == 0)
        array[pl - 1] = val;
}

print_array();

输出：
-2 2 3 4 120

时间复杂度分析 #

对于n个元素，每次插入时，平均需要遍历一半的已排序元素来找到插入位置，再移动平均一半的元素腾出空间。总的时间复杂度是O(n²)——因为每个元素的插入操作平均需要O(n)时间，n个元素累计下来就是n*O(n)=O(n²)。在最坏场景（比如输入是严格降序）下，每次插入都要遍历并移动所有已存在的元素，时间复杂度同样为O(n²)。

方案二：先填充数组再执行快速排序 #

这种方案先把所有元素按输入顺序存入数组，再调用快速排序算法对整个数组排序。对应的C代码实现如下：

int array[n];
int val;

for (int i = 0; i < n and cin >> val; ++i)
   array[i] = val;
 
print_array();

quicksort(array);

print_array();

输出：

4 2 120 -2 3 // 排序前的数组
-2 2 3 4 120 // 排序后的数组

时间复杂度分析 #

快速排序的平均时间复杂度是O(n log n)，最坏情况下是O(n²)（比如数组已完全有序或逆序），但通过随机选择基准等优化方式，可以有效避免最坏场景的频繁出现。而填充数组的过程仅为O(n)，因此整个方案的时间复杂度由快速排序主导，平均为O(n log n)。

结论 #

从时间复杂度角度来看，先填充数组再执行快速排序的方案更优——尤其是当元素数量n较大时，O(n log n)的增长速度远慢于O(n²)，性能差距会非常明显。只有当n极小（比如n<10）时，两种方案的性能差异可忽略，但对于大多数实际场景，后者的效率更高。

内容的提问来源于stack exchange，提问作者DumbProgrammer