最长距离以完全二叉树的最短。对于每个二叉比较树,必有n个内顶点与x在A 中的n种可能的情况相对应。如果一棵二叉树的所有内顶点所在的级数小于或等 于级数k,则最多有2k-1个内顶点。因此n≤2*-1,即Find(n)=k2log(n+1)1。 证毕 由定理可见,任何一种以比较为基础的算法,其最坏情况下的所用时间不可 能低于(logm)。因此,也就不可能存在其最坏情况下时间比折半搜索数量级 (阶)还低的算法。事实上,折半搜索所产生的比较树的所有外部顶点都在相邻 的两个级上,而且这样的二叉树使得由根到叶顶点的最长路径减至最小,因此 折半搜索是解决搜索问题在最坏情况下的最优算法, §2关于排序算法 问题:已知n个元素的数组A[1:n],将A中元素按不降顺序排列。 归并排序算法 程序4-2-1向有序数组插入元素 程序4-2-2插入排序 template<class T> template<class T, void Insert (t a[, int& n, const t& x)i void InsertionSort (t a[, int n) /向数组a[0:n-1]中插入元素x W/对a[0:n-1]进行排序 //假定a的大小超过n for (int i=l: i<n: i++I int Tt=alil for(i=n-1;i>=0&&x<a[i];i--) Insert(a a[i+1]=a[i] [i+1]=x; n++;//添加了一个元素 将上述两个算法合并在一起,得到下述插入排序算法 程序4-2-3插入排序算法伪代码 Insert Sort(A,n)//将A[l:n]中的元素按非降次序排列,n≥1 A[0]=-∞//生成一个虚拟值 for j from2 to n do//A[1:j1]已经排序
最长距离以完全二叉树的最短。对于每个二叉比较树，必有 n 个内顶点与x在A 中的 n 种可能的情况相对应。如果一棵二叉树的所有内顶点所在的级数小于或等 于级数 k，则最多有2 −1 k 个内顶点。因此 ≤ 2 −1 k n ，即 Find(n)=k≥log(n+1)。 证毕 由定理可见，任何一种以比较为基础的算法，其最坏情况下的所用时间不可 能低于Θ(logn)。因此，也就不可能存在其最坏情况下时间比折半搜索数量级 （阶）还低的算法。事实上，折半搜索所产生的比较树的所有外部顶点都在相邻 的两个级上，而且这样的二叉树使得由根到叶顶点的最长路径减至最小，因此， 折半搜索是解决搜索问题在最坏情况下的最优算法。 §2.关于排序算法 问题：已知 n 个元素的数组 A[1:n]，将 A 中元素按不降顺序排列。 z 归并排序算法 程序 4-2-1 向有序数组插入元素 程序 4-2-2 插入排序 template<class T> template<class T> void Insert(T a[], int& n, const T& x) void InsertionSort(T a[], int n) {//向数组 a[0:n-1]中插入元素 x {//对 a[0:n-1]进行排序 //假定 a 的大小超过 n for(int i=1; i<n; i++) { int i; T t =a[i]; for(i=n-1; i>=0 && x<a[i]; i--) Insert(a, i, t); a[i+1]=a[i]; } a[i+1]=x; } n++; //添加了一个元素 } 将上述两个算法合并在一起，得到下述插入排序算法： 程序 4-2-3 插入排序算法伪代码 InsertSort (A,n) //将 A[1:n]中的元素按非降次序排列，n≥1 A[0]=−∞ //生成一个虚拟值 for j from 2 to n do // A[1:j-1]已经排序
item=A[j]: i=j-1 while item<ALi] do//0si<j A[i+1]=A[i];i=i-1 endwhile end InsertSort while循环中的语句可能执行j次(j=2,…,n),因此最坏情况的时间限界是 j=(n(n+1)/2)-1=6(n2) 在这个算法中,大部分的时间都用在挪动元素上,随着已经排好顺序的数组 的增长,被挪动的元素的个数也在增加,而且在整个过程中,很多元素不止一次 被挪动。以下程序从某种程度上减少了这种浪费。这一算法的基本思想是采用, 分治的方法,将要排序的数组分成两部分,先对每部分进行排序,然后再将两部 分已经排好序的子数组的元素按照从小到大的顺序交替地摆放在一个新的数组 中。这一过程也许需要多次分解和组合,因而是一个递归过程。 程序4-2-4归并排序主程序伪代码 MergeSort(low,high)//A[low:high]是一个全程数组,含有 //high-low+1个待排序的元素 integer low, high if low high the mid=L(low+high)/2」//求当前数组的分割点 MergeSort(low,mid)//将第一子数组排序 MergeSort(mid+1,high)/将第二子数组排序 Merge(loW,mid,high)//归并两个已经排序的子数组 endif end MergeSort 这里我们使用了辅助程序 Merge 程序4-2-5合并过程伪代码 Merge(loW,mid,high)//已知全程数组A[low:high],其由两部分已经排
item=A[j]; i=j−1; while item<A[i] do // 0≤i<j A[i+1]=A[i]; i=i−1; endwhile A[i+1]=item; endfor end InsertSort while 循环中的语句可能执行 j 次（j=2,…,n）,因此最坏情况的时间限界是 ( ( 1)/ 2) 1 ( ) 2 2 j n n n j n ∑ = + − = Θ ≤ ≤ 在这个算法中，大部分的时间都用在挪动元素上，随着已经排好顺序的数组 的增长，被挪动的元素的个数也在增加，而且在整个过程中，很多元素不止一次 被挪动。以下程序从某种程度上减少了这种浪费。这一算法的基本思想是采用， 分治的方法，将要排序的数组分成两部分，先对每部分进行排序，然后再将两部 分已经排好序的子数组的元素按照从小到大的顺序交替地摆放在一个新的数组 中。这一过程也许需要多次分解和组合，因而是一个递归过程。 程序 4－2－4 归并排序主程序伪代码 MergeSort(low, high) // A[low : high]是一个全程数组，含有 // high-low+1 个待排序的元素。 integer low, high; if low < high then mid = (low+high)/2 //求当前数组的分割点 MergeSort(low, mid) //将第一子数组排序 MergeSort(mid+1, high) //将第二子数组排序 Merge(low, mid, high) //归并两个已经排序的子数组 endif end MergeSort 这里我们使用了辅助程序 Merge: 程序 4-2-5 合并过程伪代码 Merge(low, mid, high) //已知全程数组 A[low : high], 其由两部分已经排