【大学数据结构课件】排序1

《【大学数据结构课件】排序1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、内容提要7.1排序的基本概念7.2内部排序内部排序的分类插入排序交换排序选择排序合并排序计数排序基数排序内部排序方法比较7.3外部排序1、排序：按照结点中的某项值对集合中结点进行升序或降序的排列。2、关键字：排序时参照的数据项，有主次之分3、稳定性：如果排序操作使等值结点的相对位置(主要是指前后关系)保持不变，则排序是稳定的，否则是不稳定的。4、内部排序：排序序列放在内存中5、外部排序：需要对外存进行访问7.1排序的基本概念7.1内排序1、内部排序的分类I.按照时间复杂度来分(排序的结点数量为n)(1).简单的排序方法，O(n2)

2、(2).先进的排序方法，O(nlog2n)(3).基数排序，O(dxn)II.按照排序过程中所依据的原则来分(1).插入排序(2).交换排序(3).选择排序(4).合并排序III.按照是否改变结点的物理位置来分(1).物理重排(2).不改变结点位置的排序，包括：链地址法，利用辅助地址表排序，计数排序等算法思想：(1)已知顺序存储的待排序序列a1,a2,a3,….,an(2)假设Ak是a1,a2,..,ak序列，并已经有序，则待排序列是Akak+1,…,an,排序的基本操作是：将ak+1有序插入到Ak中，这样循环往复，直到排序完毕。

3、(3)一开始Ak={a1}(4)将ak+1有序插入到Ak中的操作：先找到插入位置，然后移动数据留出空间，再将ak+1插入内排序(cont’d)2、插入排序(1)直接插入排序voidinsort(RECTYPEr[],intn)//升序排序{RECTYPEtemp;inti,j,low,hight,m;for(i=1;i

4、+high)/2;if(r[m].key>r[i].key)high=m-1;elseif(r[m].key=high+1){r[j+1]=r[j];j--;};//移动数据r[high+1]=temp;//插入}//if}//for}内排序(cont’d)2、插入排序(1)直接插入排序内排序(cont’d)2、插入

5、排序(2)改进插入排序之一：二路插入4938659776132749Final49First38First65Final97Final9776Final13First2713First97766549Final算法思想：先将待排纪录分成若干子列分别用直接插入法排序，再对全体纪录用直接插入法排序。理论根据：直接排序序列越短越好，源序列的排序度越好效率越高。内排序(cont’d)2、插入排序(3)改进插入排序之二：希尔排序内排序(cont’d)2、插入排序(3)改进插入排序之二：希尔排序4938659776132749554一趟排序结

6、果：1327495544938659776二趟排序结果：1344938274955659776三趟排序结果：4132738494955657697算法思想：直接插入排序需要移动结点数据，如果结点数据比较大，需要移动的内存就比较多。如果建立一个辅助地址表，每个单元都指向一个结点，然后对地址表按照结点关键字进行排序，将会减少数据移动的数量内排序(cont’d)2、插入排序(4)辅助地址表的插入排序voidinsort(RECTYPEr[],intn,intt[]){//t是辅助地址表，每个单元是r中结点的下标inttemp,i,j;f

7、or(i=0;i=0&&r[t[j]].key>r[temp].key){t[j+1]=t[j];j--;}//寻找插入位置的同时，移动数据t[j+1]=temp;//插入}}}内排序(cont’d)2、插入排序(4)辅助地址表的插入排序算法思想：(1)对于n个结点的序列来说，扫描辅助地址表t的n个单元，如果发现t[i]=i，则r[i]不需要调

8、整，如果t[i]!=i，不能直接将r[i]复制成r[t[i]]，需要进入第2步(2)首先，执行temp=r[i]，保存r[i]，将i赋值给j，循环执行下面的操作：k=t[j],这时r[j]可以覆盖，覆盖成r[k]，同时令t[k]=k，j＝k。这样循