3.2比较分类堆分类

《3.2比较分类堆分类》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1§2.SortingbyComparisons（基于“比较”的分类算法）元素的结构未知2基于“比较‘的分类算法：----是最常用也是最简单的分类方法。上面介绍的基数分类需要知道变程，而基于“比较”的分类方法是：只要是线序集均可进行分类。3问题:已知n个元素的数组A[1:n]，将A中元素按非降顺序排列。4例1:程序3-2-１向有序数组插入元素TemplateVoidInsert(Ta[],int&n,constT&x){//向数组a[0:n-1]中插入元素x//假定a的存储空间大小超过ninti;for(i=n-1;i>=0&&x

2、a[i+1]=x;//添加了一个元素}在程序3-2-１中假定：a中元素在x被插入前后都是按递增的顺序排列的。插入分类算法5我们取初始数组a的大小n作为实例特征，则程序3-2-１的关键操作是x与a中元素的比较。显然，最少的比较次数为1，这种情况发生在x被插在数组尾部的时候；最多的比较次数是n，发生在x被插在数组的首部的时候。6程序3-2-２插入分类templatevoidInsertionSort(Ta[],intn){//对a[0:n-1]进行分类for(inti=1;i

3、evoidInsertionSort(Ta[],intn){for(inti=1;i=0&&t

4、分成两部分，先对每部分进行分类，然后再将两部分已经排好序的子数组的元素按照从小到大的顺序交替地摆放在一个新的数组中。以下介绍的归并分类程序，从某种程度上减少了这种浪费。这一过程也许需要多次分解和组合，因而是一个递归过程。10例２:程序3-2-４：归并分类主程序MergeSort(low,high)//A[low:high]是一个全程数组，含有//high-low+1个待分类的元素。integerlow,high;iflow

5、//将第二子数组分类Merge(low,mid,high)//归并两个已经分类的子数组endifendMergeSort归并分类算法11归并分类由分解与合并两部分组成，以含有10个元素数组的整个过程为例，可用两棵树表示出来。MergeSort(low,high)调用（分拆）过程:12Merge(low,mid,high)调用（合并）过程:Merge(1,1,2)Merge(6,6,7)Merge(4,4,5)Merge(6,7,8)Merge(9,9,10)Merge(1,2,3)Merge(1,3,5)Merge(6,8,10)Merge(1,5,10)13如果用T(n)表示归并分类所用的时

6、间，并假定合并过程所用时间与n成正比：cn，其中c是一个正数，则有:其中，a是一个常数。若n是2的方幂：n=2k，直接推导可得:14对于一般的整数n，我们可以假定，于是，得,15基于“比较”分类算法的时间下界：我们可以用决策树(判定树)来模拟分类算法，在此我们考虑最坏情况下的时间下限。在树的内部顶点上，算法执行一次比较，并根据比较的结果移向它的某一个孩子。由于每两个元素A[i]和A[j]的比较只有两种可能：A[i]

7、到外顶点路径即描述了该外顶点所代表的排列生成过程，路径的长度即是经历的比较次数。因此，比较树中最长路径的长度（其实就是比较树的高）就是算法在最坏情况下所做的比较次数。要求出所有以比较为基础的分类算法在最坏情况的时间下界，只需求出这些算法所对应的比较树的最小高度。如果比较树的高是k，则该二叉树的外顶点至多是2k个。于是，最坏情况下的最少比较次数T(n)满足。[seePage15Fig.1.18]3!