Question

5.13.总结

• 对于有序和无序列表，顺序搜索是
  $O(n)$

  O(n)。

• 在最坏的情况下，有序列表的二分查找是
  $O(logn)$

  O(logn)。

• 哈希表可以提供恒定时间搜索。
• 冒泡排序，选择排序和插入排序是
  $O(n^2)$

  O(n​2​​)算法。

• 希尔排序通过排序增量子列表来改进插入排序。它落在
  $O(n)$

  O(n) 和

  $O(n^2)$

  O(n​2​​) 之间。

• 归并排序是
  $O(nlogn)$

  O(nlogn)，但是合并过程需要额外的空间。

• 快速排序是
  $O(nlogn)$

  O(nlogn)，但如果分割点不在列表中间附近，可能会降级到

  $O(n^2)$

  O(n​2​​) 。它不需要额外的空间。