第四章 分类算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章,基本的非数值算法,分类,查找,排序方法概论,插入排序：新项插入到以前已排好的诸项适当位置上。,交换排序：若发现两项次序颠倒，交换之。,选择排序：找一个最小（或最大项），将它们同余下的分开。,枚举排序：每一项都同其它项比较，对比它小的键的个数进行计数，以确定其位置。,专用排序,直接插入,当前面,k-1,个元素分类完毕后，第,k,个元素插入到其适合位置。,0,2,3,5,6,排序：,6 3,5,2,0,6,3,5 2 0,3,6,5,2 0,3 5 6,2,0,2 3 5 6,0,最好情况,最好情况,T(n,),T(n,1)+1,T(1),0,考虑,2,个：,T(2)=1,令,最坏情况,最坏和平均情况,平均情况,(,插到,n/2),故其复杂度均为,改进：,二分插入,直接选择,原理：找出未排好最小元，置于相应位置,二重循环：,for(i,=0;in,1;i+),k=i;x=ai;,for(j,=i+1;j,n;j,+),if(ajx),k=j;x=aj;,ak=ai;ai=x;,复杂度分析：比较次数,T(n,),0+1+2+3+(n-1)=n(n-1)/2,直接交换,比较：交换相邻项直至有序,冒泡：,for(i=1;i=i;j-),if(aj-1 aj),swap(aj,aj-1);,改进：加入标志,P,：,若内循环未交换，则停止：,复杂度析,最坏情况,分类必须反复进行直到,k,1,信息论下界,令,S(n),为足以将,n,个元素排序的极小比较次数，如果一个比较树的所有内部节点都在,k,的层次内，则显然这颗树至多有,个节点。,令,k=S(n).,有：,Stirling,公式：,即：,两路归并实例,两路归并,分别加以分类，再归并为统一的经过排序的序列,将,两路归并程序,i=0;j=0;k=0,do,if(aibj),ck+=ai+;,else,ck+=bj+,while(i=m),while(jn),ck+=bj+,else,while(i,m),ck+=ai+,复杂度分析,为最后归并所作的比较（是一定值！）,考虑,个元素分类在最好情况下所需的比较次数，,某一序列每个都比较且只比较一次,其中,最坏情况下,最坏情况下,：元素交叉,1 3 5|2 4 6,堆分类,二叉树表示：线序时地址,堆：序列,满足：,注意：,堆的树根必为最小值，若插入或删除，均必须保持其堆的性质,堆的构成,二叉树表示：线序时地址,堆：序列 满足：,x/2,2x,2x+1,x,1,100,10,11,1001,101,111,110,1000,示例：,8 1 9 5 6 2 7,堆分类例,注意：,堆的树根必为最小值，若插入或删除，均必须保持其堆的性质,由二叉树构成堆,执行：,若未全排完,删去根,重建堆,第,k,层有 个节点，（,k,0,，,1,，,2,，,）,.,设二叉树高为,h,，,则顶点数,。,考虑,全二叉树,，即 ，,k,层一个点在最坏情况下要过滤到叶片需,2,(,h-k,),次比较。即每下降一层须作两次比较（与两个儿子比较，并且比它们都小时），而,k,层有 个结点。,故建堆所作比较次数,:,堆结构,堆删去最小元素,删去顶元仍保持堆的性质,每一步新元素最多下降,(),层，故堆集分类比较次数：,最坏情况比快速分类好,平均情况：,Open Problem,堆插入元素,放到最后一个元素后面，使其向上浮到合适位置,插入一元素到堆上亦需 次比较,对,x,0,，,x,1,，,，,x,N-1,分为,h,类：,k=0,1,.h-1,对,进行各自分类称为,h,分类,shell,分类,：找一个递减序列 ，,先对,作,分类，再作,分类，,，,分类。,每一类分类宜用插入法，特别后来序列分类已接近完毕时,仅需要适当,调整,（量少）。,Shell,分类,示例：,算法依据：在进行,h,分类后，再进行,k,分类，并且,kh,，,则下列关系保持：,k=0,.,h-1,引理：序列 经排序得,，,序列 经排序得 ，若 ，,i=1,2,r,则,i=1,2,r,即：取,r,4,排序后最前和最后得小于关系仍旧保持,(,实际上，,x,中对应项不会更小，而,y,中对应项也不会更大,!),证明：,在 排序后得序列,中依其从小到大得顺序为：,，,显然：,类似地,在 排序后的序列,中依其顺序排列得,，,显然,:,由于 是 的排序，,而 是 的排序，,由 ，,i=1,2,.,r,，,则,l=1,2,.,r,故,l=1,2,r,。,对于序列 条件的序列选择,Knuth,建议采用,:,得出复杂性经验公式为,:,基数分类法,分检信时：只需看邮政编码的某几位,与前述方法不同，基数分类法依表达式分类。,假定关键字,x,由,k,位数字构成：，先按最小一位分类，放在,R,个堆中,(R,为基，比如以,10,为基时,R,10),，,则堆中最低位相同，不同堆中最低位依序增加；按顺序收集起来，再对次低位分类，则可保证后两位的序关系。,重复上述过程，直到第,K,位处理完毕，分类完成。,注意：处理最后一位时，,x,k,相同的，,x,k-1,x,1,中小的将先入堆，同一堆中后面几位递增。,例：,复杂度分析：,与关键字个数,N,以及关键字长度,k,成正比，,O(kN,),。,