伪代码：
讯享网
例子：
| 改进的顺序检索 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 |
平均情况：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/12140.html