关于排序的问题

Question

气泡排序最多为O（n），最差为O（n^2），其内存使用量为O（1）。合并排序总是O（n log n），但其内存使用量为O（n）。

我们将使用哪种算法来实现一个函数，该函数接受一个整数数组并返回集合中的最大整数，假定数组长度小于1000.如果数组长度大于1000，该怎么办？

Answer 1

对于O（1）内存使用情况，可以在O（n）时间内完成对数据集的连续扫描，寻找最大值。

您只需将当前最大值设置为第一个元素，然后再遍历所有其他元素，并将当前最大值设置为该值（如果该值较大）。伪代码：

max = list[first_index] 
for index = first_index+1 to last_index: 
    if list[index] > max: 
     max = list[index] 

的复杂也不会因元素的数量列表中的改变，因此也无所谓有多少。

---

的运行时间但是会改变（因为算法是O（n）的时间），如果它发现的最大快是很重要的，有许多的可能性。当列表更改时，这些都取决于做工作，而不是每次您需要这些信息时，因此它们更适合于阅读次数多于书面次数的列表，因此可以摊销成本。

选项1是保持列表排序，以便您可以抓住最后一个元素。这是可能是矫枉过正只是保持了最大值的记录。

选项2是在您插入或从列表中删除时重新计算最大值（以及保存它的元素的数量）。对于空列表，最初将max设置为0并将maxcount设置为0。

对于插入件：

• 如果maxcount是0（该列表是空的），设置max该数值和maxcount为1
• 否则，如果该值大于max，设置max并将maxcount设置为1.
• 否则，如果此值等于max，请将1加到maxcount。

对于缺失：

• 如果这个值等于max，从maxcount减去1。
• 然后，如果maxcount为0，重新扫描列表以获得新的max和maxcount。

这样，在任何时候，你有最大的价值（计数只是一个额外的“技巧”，以加快算法，其中有超过一个元素保持最大值）。我之前在数据分析应用程序中使用过这种方法，结果比重新排序要快得多 - 在这种情况下，我必须存储最小值和最大值，但它们是相同的想法。

Answer 2

除非预分类，否则最大值始终为O（n）。如果预先分类，则较少。在搜索之前进行排序总是比O（n）更差...因此，一般来说，1,000个元素需要进行1,000次比较......只是比较字面意思。如果使用分类结构，它便宜。如果不是，它很昂贵。用分类结构插入更昂贵。 ...这就是为什么这是一个问题。