算法技术手册 – 查找 – 顺序查找

顺序查找也叫线性查找,是最简单的查找算法。穷举法遍历每个元素,查找是否包含元素t。

平均、最坏性能O(N)

如果目标元素t的分布是不均匀的,则有一些优化的方法。

  • 被找到的元素t有可能被再次找到:成功找到则移动到最前面。
  • 被找到的元素有更大可能性被找到:成功找到则向前移动一位(冒泡到前面),避免了上面方法中大量移动的耗时操作。且最终,反复被找到的元素会被冒泡到最前面。
  • 如果元素不会被多次查找到:成功找到则移动到最后。

Leave a Reply

Your email address will not be published.