【算法设计与分析qwl】伪码——顺序检索，插入排序
伪代码：
例子：
| 改进的顺序检索 Search(L,x) | |
| 输入：数组L[1...n]，元素从小到大排序，数x | |
| 输出：若x在L中，输出x位置下标 j ,否则输出0 | |
| j <- 1 while j<=n and x>L[j] do j <- j+1 if x<L[j] or j >n then j<- 0 return j |
插入排序
| 插入排序 Insert Sort(A,n) | |
| 输入：n个元素的数组A | |
| 输出：按照递增顺序排好序的数组A | |
| for j <- 2 to n do //从第2到第n个数进行插入 x <- A[j] i <- j-1 //3-7行把A[j]插入A[1..j-1] while i>0 and x<A[i] do A[i+1] <- A[i] i <- i-1 A[i+1] <- x |
|
顺序检索：
例子：检索
顺序检索算法：
实例：
最坏情况的时间估计：
在数组中或位于间隙处。
平均情况的时间估计：
假设x在L中概率是p , 且每个位置概率相等。
如果在数列里：p/n是在第i个位置的概率，第i个位置需要比较i次。对n个位置进行求和。
如果不在数列里：出现概率是(1-p) 每种情况都是n次比较。
改进顺序检索算法：
不在数组中时：比较到 x1<x<x2时就结束比较。
| 改进的顺序检索 Search(L,x) | |
| 输入：数组L[1...n]，元素从小到大排序，数x | |
| 输出：若x在L中，输出x位置下标 j ,否则输出0 | |
| j <- 1 while j<=n and x>L[j] do j <- j+1 if x<L[j] or j >n then j<- 0 return j |
时间估计：
最坏情况：W(n)=n
平均情况：
输入实例的概率分布：假设x在L中每个位置与空隙的概率都相等。
可能是：sum i =1 to n:（i * p/n ） + sum i=1 to n+1 ( i *(1-p)/(n+1) )