| 类型 | 最坏情况下查找或比较次数 | 时间复杂度 | |||||||||||||||||||||||||||||||||||
| 顺序查找 | n | O(n) | |||||||||||||||||||||||||||||||||||
| 查找最大项或最小项 | n-1 | O(n-1) | |||||||||||||||||||||||||||||||||||
| 二分查找法 | log 2 n | O(log 2 n) | |||||||||||||||||||||||||||||||||||
| 冒泡排序法 | n(n-1)/2 | O(n(n-1)/2) | |||||||||||||||||||||||||||||||||||
| 快速排序法 | n(n-1)/2 | O(n(n-1)/2) | |||||||||||||||||||||||||||||||||||
| 简单插入排序法 | n(n-1)/2 | O(n(n-1)/2) | |||||||||||||||||||||||||||||||||||
| 希尔排序法 | n r (1＜r＜2) | O(n r r))(1＜r＜2) | |||||||||||||||||||||||||||||||||||
| 简单选择排序法 | n(n-1)/2 | O(n(n-1)/2) | |||||||||||||||||||||||||||||||||||
| 堆排序 | nlog 2 n | O(nlog 2 n) | |||||||||||||||||||||||||||||||||||