各种查找方法与排序方法的时间复杂度比较

各种查找方法与排序方法的比较方法平均查找长度比较存储结构备注顺序查找(n+1) /2最大顺序、线性依次查找折半查找log2(n+l)-l最小（有序）顺序判定数分块查找log2(n/s+l)+s/2中间

各种查找方法与排序方法的比较 存储结构 备注 方法 平均查找长度 比较 顺序、线性 依次查找 顺序查找 最大 (n+1) /2 （有序）顺序 判定数 折半查找 最小 log2(n+l)-l （分块有序）顺序 建立索 分块查找 中间 log2(n/s+l)+s/2 排序方法平均时间 最坏情况 最好情况 引表 A 直接插入排序 折半插入排序 希尔排序 0(n 2)(n+4)(n-l)/2 n-1 A AA 0(n 2)(n+4)(n-l)/2 n-1 冒泡排序 O(n 2) 0(n2) A n(n-l)/2 0(21.5)n1.3 快速排序 O(nlogn) A n2 堆排序 O(nlogn) O(nlogn) 归并排序 O(nlogn)O(nlogn) 可知：（就平均时间，快速排序最好。 1） 基本有序时，直接插入法最好。 （2） 基数排序嘴稳定，当很大关键字很小时，基数排序最好。 （3）n