【算法设计与分析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) )