数据结构课件-版ds排序

第6章内部分 Slide.1-术语和约定 速分类 并分类 分数分类类0ˆ

第6章内部分 Slide.1-分类(Sorting)也叫排序(

。9 n,·7内部分类(internalsorting)和外部类(externalsorting)分类E …X¨ 9ˆ分类表

records{ key; other;recordsLIST[maxsize]第6章内部分 Slide.1-对于给定数组 ¨4 A[1].key≤A[2].key≤……如果在分类之前存在 (1≤i＜j≤n >A[i]和A[j]分别被移至A[i1]和 ¨并且i1和满足关0 6第6章内部分 Slide.1- 0,· =

˚,· ¨FI0 =0c W?–"r¨

,0c »¨] =0c第6章内部分 Slide.1- 比较关键字的次数—

1V¨b_

3交换记录位置和移动记录的次数—

& 3评价排序算法好坏的标 ①执行时间和所需的辅助空②算法本身的复杂排序算法的空间复杂若排序算法所需的辅助空间并不依赖于问题的规模 ¨即辅助空间 ¨则称之为就地排序 ceSou)非就地排序一般要求的辅助空间为O(n)（3）排序算法的时间开 … N¨,?Q决于输入实例中

第6章内部分 Slide.1- voidBubbleSort(intn,LISTA intx,yfor(i=1;i<=n-1;i++

f(n)=C3n+∑C2·(n-

2)for(j=n;j>=i+1;j--if(A[j].key<A[j-1]

当n2≥1swap(A[j],A[j-}voidswap(x,records&x,records ww=x;x=y;y=w}

T(n)=O(f(n))=PEKAPEKAVS01234567

2)=voidInsertSort(intn,LISTA inti,jA[0].key=-∞for(i=1;i<=n;i++)

第6章内部分 Slide.1-插入排序(Insertion Sort) _¿,A ],F2 。while(A[j].key<A[j-1].key)

直接插入排序:假设待排序的记录存放在 组 无序区为

ßR[1] ¿j˜从i=2起直至 j!} T(n)=O(n2)

依次将R[i]插入当前的有序区R[1..i- 生成含 。第6章内部分 Slide.1-voidlnsertSort(intn,LIST //对表R中的记录R[1..n]按递增序进行插入intfor(i=2;i<=n；i++)//依次插入if(R[i].key<R[i-{j=i-1;//R[0] 且是Ri的副{//从右向左在有序区R[1．．i-1]中查找R[i]的插入位R[j+1]=R[j]；//将关键字大于R[i].key的记录后j--}while(R[0].key<R[j].key)；//当Rikey≥Rjkey时终R[j+1]=R[0]；//Ri插入到正确的}˚算法的时间性能分

第6章内部分 Slide.1-对于具有 要进行n- 4/ │初始文件状 正 反

│无序(平均 第i趟的关│1││（i-│字比较次│││││总关键字比较次 n- │(n+2)(n- │ │第i趟记录移动次 │ │（i- │总的记录移动次 │(n- │ │时间复杂 │ │ │ ˚算法的空间复杂度分˚直接插入排序的稳定第6章内部分 Slide.1- 于 ˙ x

Œ’ ´直至所取的增 - 第6章内部分 Slide.1- void Pass(LISTR，int ¿为当前fori=d+1;i<=n；i+将R[d+1．．n]分别插入各组当前的有序区{j=i-d；//R[0] do{ R[j+d]=R[j]；//后移记录j=j-d；//查找前一R[j+d]=R[0]；//插入R[i]到正确的位置}} 第6章内部分 Slide.1-void Sort(LIST{do

不妨设increment=increment/3+1；//求下一增 Pass(R，increment)；//一趟增量为increment的 入排} 当增量 Pass和 08$¨只是由于有哨兵而在内循环中增加了一个循环判定条件 ¨以防下标+|第6章内部分 Slide.1-例如：关键字为493865977613274955增量序列为:5,13274955一趟结果 386597二趟结果 556597三趟结果:41327384949556576算法分 ˚增量序列的选 ˛G。 ①最后一个增量必须为②应该尽量避免序列中的值(尤其是相邻的值 第6章内部分 Slide.1- WG,· n*l.25到1.6*n*1.25 {L2．S 排序的时间性能优于直接插入排 -

pM0," 当 ?&和 即直接插入排序的最好时间复度O(n) 时间复杂度(n2) =③ ˛G¨‡6

J¨!4

-

后来增量

F9¨ ¿E!¨<D´¿ F9¨ ¿E!¨<D´¿ 9E‡3<D´¿_¿¶。F第6章内部分 Slide.1-1.线性选选最小的放在余下的n-1个中选项最小放重复直到结voidSelectSort(intn,LISTA inti,j，lowindexkeytypefor(i=1;i<n;{lowindex=i;lowkey=A[i].key;for(j=i+1;j<=n;i++)lowkey=A[j]lowindex=j}swap(A[i],A[lowindex])} T(n)=O(n2)

PEPEKAVS1234567第6章内部分 Slide.1-voidsort(intn,int{intb[],i,for(i=0;i<n;for((i=0;i<n;for(j=0;j<n;if(a[i].key<a[j].key)

for(i=0;i<n;i++)for(j=0;j<n;j++)第6章内部分 Slide.1-n把序列划分 个子序列,不是完全平方,向上取值n(2)建立与每一个子序列相对应的辅助工作单元,即二级存贮单元(3)利用线性选择,分别找出各子序列的最小关键字存入二级单元4利用线性选择在二级单元中找出最小的输行5)(5)对全序列中具有最小单元的子序列,再次扫描,找出次小的送二级单元,再执行(4)重复执行45取尽为止.每次选择后标记例:F={8,7,2,5,4,6,9,1,3}共9个结点,划分成3个子序2*4 74124第6章内部分 Slide.1- 是分治策略(一般与递归技术结合使用)，以减少分类过程之中0ˆ分解

N¨-

¨0 求解:

O则直接求组合

ˇL 第6章内部分 Slide.1-设被分类的无序区为 >˜文件 中的一个记录(数据元素)的关键字v作为准元素(控制关键字通过基准元素v把表(文件,数据集合) @ˆ 重复 6 9¨

>|； 9 61.扫描2.测试3.交第6章内部分 Slide.1-9ˆ

,·

¡ ˜ ı） &¨划分次数为

¨全部比较次数 ¨交换次数(n/6)log2n下标kvA[i].key，A[(i+j)/2].keyA[j].key的中值

v=从A[i].key到

],·

=- =Ai] 第6章内部分 Slide.1-/*设A是外部数组 FindPivot(inti,intj/*若 -(¨<返回 I¨左边两个不同关键字中的较大者的下标 intk

firstkey/*第1个关键字的值A[i].key/*从左到右查找不同的关键字fork=i+1;k<=jk*扫描不同的关键字ifA[k].keyfirstkey*选择较大的关键字*/returnk;elseif(A[k].key<firstkeyreturni;return0;}第6章内部分 Slide.1-、表的划分(分割)扫描令游标l从左端(初始时li¨直到遇到

¨越过关键字小于v的所有又令游标r从右端(初始时r=j ¨越过关键字大于等于的所有记录,直到遇到测试l和 若l<r,则转(3 ¨否则(l>r,即l=r+1)转(4 ¨转(1)；(目的是使l和r都至少向其前进方向前此时A[i],…A[j]被划分成为满足条件的两部分A[i],…A[l-1]和A[l],…,A[j]第6章内部分 Slide.1-intPartition(inti,intj,keytypepivot/*划分 ¿G关键字≥pivot·{intl,r;

返回有子序列的起始下标for(l=i;A[l].key<pivot;l++)for(r=j;A[l].key>=pivot;r--)if(l<r}while(l<=r l}

[i,……,j[i,…k-1,k,k+1,…j第6章内部分 Slide.1-voidQuickSort(inti,intj/*对外部数组A的元素A[i],…,A[j]进行快速分类{keytypeintk;//关键字大于等于pivot的记录在序列中的起始下标intpivotindex;//关键字为pivot的记录在数组A中的下标pivotindex=FindPivot(i,j);ifpivotindex0//递归终止k=Partition(i,j,pivot);QuickSort(i,k-1);QuickSort(k,j);}}//对数组A[1],…,A[n]进行快速分类可调用QuickSort(1,n)实第6章内部分 Slide.1-3v114v 26v5324v339v6v5533456591123345569556快速分类算法非递归

第6章内部分 Slide.1-voidQuickSort(recordsR，intn{structintup;intstructstackinttop;elementdata;第6章内部分 Slide.1-while(s->top!=0)/*栈不空,取一序列划分 l=s->data[s-j=r;temp=R[i];/取第一个元素作为基准dowhile(i<j&&R[j].key>=temp.key) whlie(i<j&&R[i].key<temp.key)i++;swap(R[j],R[i]);}while(i<=j第6章内部分 Slide.1-ifi+1r*右序列多于2个记录{s-s->data[s->top]s->data[s-}ifi-1l*左序列多于2个记录{s-}为了不导 的划分,选取基准最好的方法是用一个随函数产生一个位于I和J这间的随机数K,有R[K]作为基准,相当于强迫R[]中的记录随机分布第6章内部分 Slide.1- ¨对长度为

情况是每次划分选取的基准都是当前无序区中关键字最小(或最 6<B6p˙,·0ZM0“,·jL$]A¨仅仅-比划分前的无序区中 A0Z ¨快速排序必须做n- 6¨第i次划分开始时区间长度为 ¨所需的比较次数为n-i(1≤i≤n- ： 61 那么当文件的记录已按递增序(或递减序 是当前无序区中关键字最小(或最 0

每次划分所取的基准¨则快速排序所需的比较2）最好时间复杂

第6章内部分 Slide.1- ;¨每次划分所取的基准都是当前无序区的"中值 1

W8$-1y递归树的高度为

˜$1j! ¨而递归树每一层上结点所对应的划分过程中所需要的关键字比较次数总和不超过 ¨故整个序过程所需要的关键字比较总次数C(n)=O(nlogn , 空间复杂 )!B!Q j 其递归树的高度为 ¨故递归后需栈空间为 ;¨归树的高度为 ¨所需的栈空间为O(n)稳定 ·如[2，2，1第6章内部分 Slide.1- _ ˜89 •

L <2«,· •&并 62˜ ¿ 自底向上和自顶向 ¿˜设A[left],…,A[mid] A[mid+1],…,A[right]

。 ƒ 0§成一个分类B[left],

合并为一堆且有序 ˜实现函数 第6章内部分 Slide.1-voidMerge(intleft,intmid,intright,LISTA,LIST],…,,…,B[left intileft;jmid+1,kleft置初while(i<=mid&&j<=rightB[k++]=(A[i].key<=A[j].key)?A[i++]:A[j++]/*两个序列非空时，取小者输出到B[k]while(i<=mid B[k++]=A[i++]/*若第一个子序列非空(未处理完)， 剩余部分到Bwhile(j<=right B[k++]=A[j++]/*若第二个子序列非空(未处理完)， 剩余部分到B}时间复杂性：O(right－left＋1 空间复杂性：O(right－left＋1第6章内部分 Slide.1-

共

Z¨将它们两两合并成n/2 每个序列长度为 最后一个序列长度为1）对n/2 ƒ；

j! {11} { 26 { 77 { 61 { 59 { 48{ 77 { 61}{ 48{ {

77}{ 48 77第6章内部分 Slide.1-第1遍归并的子序列长度为20，第2遍为21，…，第i遍为2i-1，所以由2i-，对于log2O(nlog2n)。子文件，故称其为"二路归并排序"。类似地有k(k>)路归并排序后一个子序列的长度可能小于len，此时应注意最后一个子序列的下第6章内部分 Slide.1-当子序列的个数为奇数时，则最后一个子序列无需与其它子序列归并（轮空），直 到归并序列之后即可总之，每遍归并时，必须对子序列的个数是奇数、以及最后一个子序长度可能小于len两种特殊情况进行特殊处理 {11} { 26 { 77 { 61 { 59 { 48{ 77 { 61}{ 48{ {

77}{ 48 77第6章内部分 Slide.1-执行一遍归并的算法/*把A中长度为len的相邻序列归并成长度为2*len的序列的函数voidMpass(intn,intlen,LISTA,LIST/*把A中长度均为len的相邻两个分类子序列归并入B，ｎ为A的记录总数{inti,tfor(i=1;i+2*len-1<=n;i+=2*lenMergei,i+len-1i+2*len-1AB);/*归并长度为len的两个分类子序列ifi+len-1n /*尚有两个子序列，其中最后一个长度小于Mergeii+len-1nAB /*归并最后两个子序列 /*若i<=n且i+len-1>=n时，则剩余一个子序列轮空，直 for(t=i;t<=n;t++)B[ｔ]=A[ｔ]; /*Mpass第6章内部分 Slide.1-voidSort(intn,LISTA /*二路归并分类intlen1*当前归并子序列的长度，初始为1LISTBwhile(len<Mpass(n,len,A,B)len=2*lenMpass(nlenBA*A、B互换位置*/len=2*len;}}/*MergeSort第6章内部分 Slide.1-自然归并排序（naturalmergesort）是基本归并排序的一种变化。它首先对输入序列中已经存在的有序子序列进行归并。例如，元素序列4，8，3，7，1，5，6，2中包含有序的子序列[4，8]，3，7]，1，5，6]和[2]，这些子序列是按从左至右的顺序对元素表进行扫描而产生的。（若位置i的元素比位置i1的元素大，则从位置i进行分割）对于上面这个元素序列，可找到四个子序列，子序列1和子序列2归并可得[3478，子序列3和子序列4归并可得1256，最后，归并两个子序列得到[1,2,3,4,5,6,7,8]。因此，对于上述元素序列， 需要进行[log2n]趟归并。因此自然归并排序将在O(n)的时间内完成排序,而将普通归并花费O(nlogn)的时间。自底向上的归并算法效率较高，但可读性差若采用分治技术自顶向下的算法，形式简洁第6章内部分 Slide.1-归并分 算法思想(分治思想简单地将原始序列划分为两个子分别对每个子序列递归排最后将排好序的子序列合并为一个有序序列，即归并过步骤如果待排序的项数为0或1，返回对等的两部分分别的递将排好的两部分归并为一个有序第6章内部分 Slide.1-第6章内部分 Slide.1-分解：将当前表区间一分为二，即 mid=(low+high)/2求解：递归地对表分区A[low],…,A[mid]和A[mid+1],…,进行归并分类组合注意：递归的终止条件是子区间长度为1，因为一个记录自然有序归并分类的分治递归

第6章内部分 Slide.1-voidSort(LISTA,LISTB,intlow,inthigh/*用分治法对A[low],…,A[high]进行二路归并 intmid=(low+high)/2iflow<high*区间长度大1，high-low>0Sort(A,B,low,mid);Sort(A,B,mid+1,high);Merge(low,mid,hight,A,B)} /*Sort注：归并分类是稳定分类第6章内部分 Slide.1-算法Sort的执行过程如下图所示的递归树第6章内部分 Slide.1-这棵归并树与快速排序类似,但会发现前而后者”分解”较难.时间复杂对长度为n的文件，需进行logn趟二路归并，每趟归并的时间为 空间复杂需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助间复杂度为第6章内部分 Slide.1-一趟排序。一趟选出的关键字最小的记录称为“冠军”，而“亚军”是从与“冠军”比较失败的记录中找出。输出“冠军”后，将（冠军）第6章内部分 Slide.1-对关键字序列72,73,71,23,94,16,05,68进行树形选择排第6章内部分 Slide.1-“亚军”是从与“冠军”比较失败的记录中找出的∞第6章内部分 Slide.1-例:一组待排序的记录的关键字初始如下第一步

第6章内部分 Slide.1-n个记录的锦标赛排序，每选择一个记录需缺点：需要较多的辅 与“最大值”进行多次多余的比较。对树形排序的改进是

第6章内部分 Slide.1-若2*i≤n，则A[i].keyA[2*i].key;A[2*i+1].key; 或(1若2*i≤n，A[i].key≥A[2*i].key

第6章内部分 Slide.1- :,·K^= ƒˆ右儿子结点上的关˜即A[ ]¨ ’f_[6‘ ¯ 。 ]

˜,·¯6¨

。1 3 311233946112339465541592653第6章内部分 Slide.1- ”

˜8 G用完全二叉树的数 结构把数组所对应的完全二叉树以堆不断扩

/j 令i=n/2,…,2,1分别把以n/2,…,2,1为根的完全二叉树 即执行算法PushDownin 6«令in,n1交换 ?, ˜当前最大的叶结 7,· ¨即执行整理:把剩余的i- @即执行PushDown(1,i- ;1],A[2],…,A[n] 按关键字有的数据集堆(按关键字有的数据集堆(建堆待分类数据集完二叉第6章内部分 Slide.1-voidHeapSort(intn,LISTA intfor(i=n/2;i>=1;i /*初始建堆，从最右非叶结点开始 /*整理堆，把以i为根，最大下标的叶为swap(A[1],A[i]);/*堆顶与当前堆中的下标最大的叶结点交换PushDown(1,i-/*整理堆把以1为根，最大叶下标为i-1的完全二叉树整理成堆}}T(n)=O(nlog2n第6章内部分 Slide.1-四、整理堆算法：PushDown(first该操作的功能是把以Afirst为根，以Alast]为最后一个结点的完全二元树整理A[first],…,A[last])具体操作如下子交换）。重复上述过程，直到以A[first]为根的完全二叉树是堆为止。算法如下第6章内部分 Slide.1-voidPushDown(intfirst,int intr=first; /*r是被下推到的适当位置，初始值为根first*/while(r<=last/2)/*A[r]不是叶，否则是堆*/if((r==last/2)&& /*r有一个儿子在2*r上且为左儿子swap(A[r],A[2*r]);/*下推r=last/*循环结束

}第6章内部分 Slide.1-else swap(A[r],A[2*r]);//与左儿子交换r=2*r;//下推到的位置}else r=2*r+1;/*下推到的位置也是下次考虑的根*/}else/*A[r]符合堆的定义，不必整理，循环结束O(log2(last/first))=O(log2

339253第6章内部分 Slide.1-3392533434392655394653946553126565 393946551123394655 1

第6章内部分 Slide.1-2 6第6章内部分 Slide.1-五、时间复PutDown函数中，执行一次while循环的时间是一个常数。因为r每次至少为原来的两倍，假设while循环执行次数为i，则当r从first变为first*2i时循环结束。此时r=first*2i>last/2ilog(last/first)-1)。所以while循环体最多执行log2(last/first)次，即PushDown时间复杂性O(log(last/first))=Olog2n)。∴HeapSort时间复杂性O(nlog2六、不稳定的，举出反习题

第6章内部分 Slide.1-54510840数据结构的定义如下DP是一棵完全二元树,它或是一空树,或满足下列情况:1.;2.若左子树是小根堆;3.,若这样的结点不存在则取j为右子树中与i的父结点相对应的结点结点i54510840问题:1.插入结点4的结果;2.描述插入新结点的算法第6章内部分 Slide.1-6.5 理论上可以证明，对于基于关键字之间比较的分类，无论用什么方法至少需要进行log2n!次比较由Stirling 可知，log2n!。所以基于关键字比较的分类时间的下界是)此不存在时间复性低于此下界的基于关键字比较的分类!只有不通过关键字比较的分类方法,才有可能突破第6章内部分 Slide.1-一、基数分类（时间复杂性可达到线性级（基数分类）。因此基数分类又称为桶分类。显然，要求关键字分量的取值范围必须是有限的，否则可箱二、算法的基本不相同时取位数的最大值个分量，每个分量的值取值0,1,…,9,第6章内部分 Slide.1-首先把全部数据装入一个排队 ¨然后按下列步骤进行初态:设置 D 分配:依次从排队中取出每个数据 第 data.key右第 ¨设其为到

¨把data插入排队 ¨则全部数据被分 ¿¨把每个数据插入排队A。

¨并按照取重复

¨对于关键字中有figure位数字的数据进行 4*6¨即 ¿,· 第6章内部分 Slide.1-321 789 Q[8]:986987789 Q[9]:890 Q[9]: 890210321901432012123543765 901109210012018321123432543 987 018098109123310321432543678 890901 第6章内部分 Slide.1- Radix(intk, p{intpower, Radix(intk, p{intpower,i;power=1;for(i=1;i<=p-1;i++power=power*10return((k%(power*10))/power)}{QueueQ[10];recordsdata;intpass,r,i;for(pass=1;pass<=figure;pass+)fori=0i<=9i++)/*置空队列Makenull(Q[i])whileEmptyA*分配data=Front(A)DeQueue(A)for(i=0;i<=9;i++){}/*大大缩短收集操作的时间r=for(i=0;i<=9;i++){}/*大大缩短收集操作的时间fori=0i9i