大门|大门-CS-2016（第1组）|问题23

插入排序、合并排序和快速排序的最坏运行时间分别为：

（A） Θ（n logn）、Θ（n logn）和Θ（n） ^2. )

（B） Θ（n） ^2. )，Θ（n） ^2. )和Θ（n logn）

（C） Θ（n） ^2. )，Θ（n logn）和Θ（n logn）

（D） Θ（n） ^2. )，Θ（n logn）和Θ（n） ^2. ) 答复: （D） 说明：

• 插入排序 取Θ（n） ^2. )在最坏的情况下，我们需要运行两个循环。外部循环需要逐个拾取要插入到正确位置的元素。内循环用于两件事，找到要插入的元素的位置，并将所有已排序的较大元素向前移动一个位置。因此，最坏情况下的递归公式是T（n）=T（n-1）+Θ（n）。
• 合并排序 在所有情况下都需要Θ（n logn）时间。我们总是把数组分成两半，对两半进行排序并合并。递推公式为T（n）=2T（n/2）+Θ（n）。
• 快速排序 取Θ（n） ^2. )在最坏的情况下。在快速排序中，我们以一个元素为轴心，并围绕它对数组进行分区。在最坏的情况下，拾取的元素总是一个角元素，递归公式变成T（n）=T（n-1）+Θ（n）。最坏情况发生时的一个例子是，数组被排序，我们的代码总是选择一个角元素作为轴心。

这个问题的小测验