建立/插入到排序列表中

Question

下面是一个问题：你有一组N个随机数被插入一个排序列表（从小到大）。 建筑物整个列表中最糟糕的渐进时间表现是什么？我知道如何用几种语言在代码中插入排序列表（我知道有几种不同的方式）： 我有程序检查数组中是否还有空间存在一个项目。然后，要将项目插入列表中，列表中所有大于要插入项目的项目都会通过for循环移动到右侧。然后我有一个指向要插入的项目被记录在适当的数组位置。 在C++中：

void SortedListAsArray::Insert (Object& object) 
{ 
    if (count == array.Length()) 
     throw domain_error ("list is full"); 
    unsigned int i = count; 
    while (i > 0 && *array [i - 1U] > object) 
    { 
     array[i] = array [i - 1U]; 
     --i; 
    } 
    array[i] = &object; 
    ++count; 
} 

这是我认为的O（n）时间。令我困惑的是整个“建设”整个清单部分。我不确定这是否意味着从这些数字开始建立一个列表，然后插入它们然后进行排序，或者只是将一组数字插入到已排序的列表中。你们认为这意味着什么，它会改变我的跑步时间吗？谢谢！

Answer 1

想通了。如果我使用两个for循环以不同的方式（并且更容易）做到这一点，那将是O（n^2）。我假设已经有一个排序列表，我只是使用插入排序来插入数字。