第四章 分类算法.ppt

1、第四章 基本的非数值算法,分类 查找,排序方法概论,插入排序：新项插入到以前已排好的诸项适当位置上。 交换排序：若发现两项次序颠倒，交换之。 选择排序：找一个最小（或最大项），将它们同余下的分开。 枚举排序：每一项都同其它项比较，对比它小的键的个数进行计数，以确定其位置。 专用排序,直接插入,当前面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(n1)+1 T(1)0 考虑2个：T(2)=1,令,最坏情况,最坏和平均情况,平均情况(

2、插到n/2),故其复杂度均为 改进：二分插入,直接选择,原理：找出未排好最小元，置于相应位置,二重循环： for(i=0;in1;i+) k=i;x=ai; for(j=i+1;jn;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：若内循环未交换，则停止：,复杂度析,最坏情况 分类必须反复进行直到k1,信息论下界,令S(n)为足以将n个元素排序的极

3、小比较次数，如果一个比较树的所有内部节点都在k的层次内，则显然这颗树至多有 个节点。 令k=S(n).有：,Stirling公式：,即：,两路归并实例,两路归并,分别加以分类，再归并为统一的经过排序的序列,将,两路归并程序,i=0;j=0;k=0 do if(ai=m) while(jn) ck+=bj+ else while(im) ck+=ai+ ,复杂度分析,为最后归并所作的比较（是一定值！）,考虑,个元素分类在最好情况下所需的比较次数，,某一序列每个都比较且只比较一次,其中,最坏情况下,最坏情况下：元素交叉1 3 5 | 2 4 6,堆分类,二叉树表示：线序时地址,堆：序列,满足：,注

4、意：堆的树根必为最小值，若插入或删除，均必须保持其堆的性质,堆的构成 二叉树表示：线序时地址 堆：序列 满足：,x/2,2x,2x+1,x,1,100,10,11,1001,101,111,110,1000,示例：8 1 9 5 6 2 7,堆分类例,注意： 堆的树根必为最小值，若插入或删除，均必须保持其堆的性质 由二叉树构成堆 执行：若未全排完 删去根 重建堆,第k层有 个节点，（k0，1，2，）. 设二叉树高为h，则顶点数 。 考虑全二叉树，即 ，k层一个点在最坏情况下要过滤到叶片需2(h-k)次比较。即每下降一层须作两次比较（与两个儿子比较，并且比它们都小时），而k层有 个结点。 故建堆

5、所作比较次数:,堆结构,堆删去最小元素 删去顶元仍保持堆的性质,每一步新元素最多下降( )层，故堆集分类比较次数： 最坏情况比快速分类好 平均情况：Open Problem,堆插入元素 放到最后一个元素后面，使其向上浮到合适位置 插入一元素到堆上亦需 次比较,对x0，x1，xN-1 分为h 类： k=0,1,.h-1 对 进行各自分类称为h分类 shell 分类：找一个递减序列 ， 先对 作 分类，再作 分类， 分类。 每一类分类宜用插入法，特别后来序列分类已接近完毕时 仅需要适当调整（量少）。,Shell分类,示例：,算法依据： 在进行h分类后，再进行k分类，并且kh，则下列关系保持： k=

6、0,.,h-1 引理：序列 经排序得 ， 序列 经排序得 ， 若 ，i=1,2,r,则 ,i=1,2,r,即：取r4 排序后最前和最后得小于关系仍旧保持(实际上，x中对应项不会更小，而y中对应项也不会更大!),证明： 在 排序后得序列 中依其从小到大得顺序为： ， 显然： 类似地,在 排序后的序列 中依其顺序排列得 ， 显然: 由于 是 的排序， 而 是 的排序， 由 ，i=1,2,.,r，则 ,l=1,2,.,r 故 ,l=1,2,r。,对于序列 条件的序列选择 Knuth建议采用: 得出复杂性经验公式为:,基数分类法,分检信时：只需看邮政编码的某几位 与前述方法不同，基数分类法依表达式分类。 假定关键字x由k位数字构成： ，先按最小一位分类，放在R个堆中(R为基，比如以10为基时R10)，则堆中最低位相同，不同堆中最低位依序增加；按顺序收集起来，再对次低位分类，则可保证后两位的序关系。 重复