大学数据结构课件排序

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

2、的分类(1).简单的排序方法，o(n2)(2).先进的排序方法，o(nlog2n)(3).基数排序，o(dxn)(1).插入排序(2).交换排序(3).选择排序(4).合并排序(1).物理重排(2).不改变结点位置的排序，包括：链地址法，利用辅助地址表排序，计数排序等算法思想算法思想：(1)已知顺序存储的待排序序列a1,a2,a3,.,an(2)假设ak是a1,a2,.,ak序列，并已经有序，则待排序列是akak+1,an,排序的基本操作是：将ak+1有序插入到ak中，这样循环往复，直到排序完毕。(3)一开始ak=a1(4)将ak+1有序插入到ak中的操作：先找到插入位置，然后移动数据留出空间

3、，再将ak+1插入2、插入排序、插入排序(1) 直接插入排序直接插入排序void insort(rectype r, int n) /升序排序rectype temp; int i, j, low, hight, m; for(i=1;in;i+) /r0已经有序，从r1开始 if(ri.keyri-1.key) /准备插入 low=0; high=i-1; /折半查找法，寻找插入位置 while(lowri.key)high=m-1; else if(rm.key=high+1)rj+1=rj; j-; ; /移动数据 rhigh+1=temp; /插入 / if /for2、插入排序、插入

4、排序(1) 直接插入排序直接插入排序2、插入排序、插入排序(2) 改进插入排序之一：二路插入改进插入排序之一：二路插入49 38 65 97 76 13 27 49final49first38first65final97final9776final13first2713first97766549final算法思想：先将待排纪录分成若干子列分别用直接插入法排序，再对全体纪录用直接插入法排序。 理论根据：直接排序序列越短越好，源序列的排序度越好效率越高。2、插入排序、插入排序(3) 改进插入排序之二：希尔排序改进插入排序之二：希尔排序2、插入排序、插入排序(3) 改进插入排序之二：希尔排序改进插入

5、排序之二：希尔排序 49 38 65 97 76 13 27 49 55 4 一趟排序结果： 13 27 49 55 4 49 38 65 97 76二趟排序结果： 13 4 49 38 27 49 55 65 97 76三趟排序结果： 4 13 27 38 49 49 55 65 76 97 算法思想算法思想：直接插入排序需要移动结点数据，如果结点数据比较大，需要移动的内存就比较多。如果建立一个辅助地址表，每个单元都指向一个结点，然后对地址表按照结点关键字进行排序，将会减少数据移动的数量2、插入排序、插入排序(4) 辅助地址表的插入排序辅助地址表的插入排序void insort(rectyp

6、e r, int n, int t)/t是辅助地址表，每个单元是r中结点的下标 int temp, i, j; for(i=0;in;i+) ti=i; /初始化辅助地址表 for(i=1;in;i+) if(rti.key=0&rtj.keyrtemp.key) tj+1=tj; j-; /寻找插入位置的同时，移动数据 tj+1=temp; /插入 2、插入排序、插入排序(4) 辅助地址表的插入排序辅助地址表的插入排序算法思想算法思想：(1)对于n个结点的序列来说，扫描辅助地址表t的n个单元，如果发现ti=i，则ri不需要调整，如果ti!=i，不能直接将ri复制成rti，需要进入第2

7、步(2)首先，执行temp=ri，保存ri ，将i赋值给j， 循环执行下面的操作： k=tj, 这时rj可以覆盖，覆盖成rk，同时令tk=k，jk。这样循环直到遇到tji为止。这时跳出循环，执行rj=temp; 并转到(1)2、插入排序、插入排序利用辅助地址表的对结点进行物理重排利用辅助地址表的对结点进行物理重排35 14 12 42 26 50 31 170 1 2 3 4 5 6 7217460350 1 2 3 4 5 6 735void rearrange(rectype r, int t, int n) rectype temp; int i, j, k; for(i=0;i=n;i

8、+) if(ti!=i) temp=ri; j=i; while(tj!=i) k=tj; rj=rk; tj=j; j=k; rj=temp; tj=j; 2、插入排序、插入排序利用辅助地址表的对结点进行物理重排利用辅助地址表的对结点进行物理重排void bubblesort(rectype r,int n) rectype temp; int i, j; for(i=1;in;i+) for(j=0;jrj+1.key) temp=rj; rj=rj+1; rj+1=temp; 时间复杂度时间复杂度：o(n2)3、交换排序、交换排序(1) 直接交换排序直接交换排序(冒泡排序冒泡排序)(1)

9、 直接交换排序直接交换排序(冒泡排序冒泡排序)改进思想改进思想：(1) 一旦某趟起泡过程中没有发生冒泡，就结束算法(2) 记下没有发生冒泡的区间k.n-i，下次冒泡终点就是k-1(3) 利用传送代替交换，当遇到ak需要上冒时，并不交换数据，而是将后序比它小的数据向前移动，直到遇到aj比ak大为止，然后将ak放到aj的前面。(4) 可以交替地从左向右上冒和从右向左下沉3、交换排序、交换排序void bubblesort(rectype r, int n) int x=0, y=n-1, t=1, d=1, j, s; /*x.y是起泡区间,d是起泡方向,s是待起泡地结点关键字的值，t既表明是否发

10、生冒泡操作，也标识着下一趟起泡的终点*/ rectype temp; while(t)/t标识是否发生了冒泡 j=x; s=rj.key; temp=rj; t=0; while(j*dy*d) if(s*dlow&rhigh.key=pivotkey)high-; /下行 if(highlow) /下行时遇到了比pivotkey小的结点 rlow=rhigh; low+; while(highlow&rlow.keylow)/上行时遇到了比pivotkey大的结点 rhigh=rlow; high-; /while rlow=temp; *pivotloc=low; void

11、 quicksort(rectype r, int low, int high) int k; if(lowhigh) part(r,low,high,&k); quicksort(r,low,k-1); quicksort(r,k+1,high); 快速排序算法快速排序算法4、选择排序、选择排序void selectsort(rectype r, int n) rectype temp; int i, j, k; for(i=1;in;i+) k=i; for(j=i+1;j=n;j+) if(rj.keyrk.key) k=j; if(k!=i) temp=ri; ri=rk; r

12、k=temp; /for (1) 直接选择排序直接选择排序4、选择排序、选择排序(2) 树型选择排序树型选择排序也叫锦标赛排序133813386527493827137613496597两两比较n/2次选出最小值4、选择排序、选择排序(2) 树型选择排序树型选择排序先将最小值由顶向下去掉，最底层换上maxint再比较log2n次。重复这一过程n-1次得到全排序序列时间复杂性38386527493827764965977627274、选择排序、选择排序(3) 堆排序堆排序堆：在n个结点的顺序存储的完全二叉树中，所有双亲结点值都大于(或小于)它的孩子结点值，这个二叉树就称为大顶堆大顶堆(小顶堆)或

13、者极大堆极大堆(极小堆)。根称为堆顶，最后的叶子称为堆底。13492797657638小顶堆13 49 27 97 65 38 76 0 1 2 3 4 5 6 74、选择排序、选择排序(3) 堆排序堆排序堆排序的好处堆排序的好处：比比赛树更省空间，同时保留了低时间复杂度堆排序的基本思路堆排序的基本思路： 如果进行升序排列，则先建立大顶堆，然后将堆顶与堆底交换，舍弃堆底，将剩余的部分再次建立大顶堆，依次类推。如果进行降序排列，需要建立小顶堆。需要解决的两个关键问题需要解决的两个关键问题：(1)如何将初始序列建立成一个初始堆(2)堆顶与堆底交换后，舍弃堆底，剩余的部分不再是堆，如何将剩余的部分调

14、整成堆4、选择排序、选择排序堆的调整算法堆的调整算法操作条件：操作条件：堆顶的子树都是堆，但整个二叉树不是堆堆顶的子树都是堆，但整个二叉树不是堆算法思想算法思想：将堆顶元素向下沉，向下沉的过程中，选择较大或较小的一个子树进行。这样一直沉到该元素为根的子树是堆为止。624725297213351974837946908197199719298390194、选择排序、选择排序算法思想算法思想：建立初始堆的过程就是自底向上调整堆的过程。因为，完全二叉树的叶子结点本身是堆，从下向上从右向左依次调整非叶子结点，使之成为堆，这样一直调整到根。建立初始堆的算法建立初始堆的算法void adjust(rect

15、ype r, int k, int n)/大顶堆的调整算法/*rk后面序列是堆，调整以rk为根的序列成为堆*/ rectype temp; int i, j; i=k; j=2*i; temp=rk while(j=n) if(jn&rj.keyrj+1.key)j+; /寻找值较大的孩子 if(temp.key=1;i-) adjust(r,i,n);/n/2是从后面数第一个非叶子 for(m=n; m=2;m-) temp=r1; r1=rm; rm=temp; /堆顶与堆底交换 adjust(r,1,m-1); /重新调整成堆 时间复杂度o(nlog2n)堆排序算法堆排序算法5、

16、合并排序（归并排序）、合并排序（归并排序） 将两个或两个以上有序表组合成一个新的有序表 叫做。 将一个序列看成是n个由单个元素组成的子序列，每个子序列都是有序的长度为1。 再将这些子序列两两合并，得到n/2个长度为2的有序子序列。继续两两合并，直到合并成一个长度为n的有序序列。每次合并，子序列的长度都成倍增长。归并排序需要开辟一个辅助空间存放中间状态和最后的结果。5、合并排序（归并排序）、合并排序（归并排序）49 38 65 97 76 13 27 4938 49 65 97 13 76 27 4938 49 65 97 13 27 49 7613 27 38 49 49 65 76 97o(

17、nlogn)5、合并排序（归并排序）、合并排序（归并排序）void segmentmerge(rectype r1,rectype r2, int p,int m, int n)/*r1p.m和r1m+1.n是相邻的有序段，本算法将它们合并后存放到r2p.n中*/ int i, j, k; i=p; k=p; j=m+1; while(i=m&j=n) if(r1i.key=r1j.key)r2k+=r1i+; else r2k+=r1j+; while(i=m) r2k+=r1i+; /将剩余的部分续接到r2中 while(j=n) r2k+=r1j+;void passmerge(

18、rectype r1, rectype r2, int len ,int n)/*len是本趟合并的有序子段的长度，n是待排序列的长度,本算法完成一次长度为len的归并*/ int k; k=1; while(k+2*len-1=n) /还有至少2个长度是len子段没有合并 segmentmerge(r1,r2,k,k+len-1,k+2*len-1); k+=2*len; if(k+len-1n)/最后一对有序段，最后一段长度不足len的情况 segment(r1,r2,k,k+len-1,n); else /只剩下一个有序段 while(k=n) r2k=r1k; k+; void mer

19、gesort(rectype r,rectype r2,int n)/归并排序 int len; len=1;/子段长度初始化为1 while(lenn) passmerge(r,r2,len,n); len*=2; passmerge(r2,r,len,n); len*=2; 算法思想算法思想：(1)设置一个数组，存放待排序列各结点的计数信息。结点的计数信息是指比该结点小或大的其他结点的个数。(2)一开始所有的结点计数都为1，针对每个结点，遍历其他结点，当遇到比当前结点大或小的结点时，结点计数增1。(3)结点的计数即是结点的排序序号6、计数排序、计数排序void countsort(rect

20、ype r,int count,int n) int i, j; for(i=0;in;i+) counti=1; for(i=0;in-1;i+) for(j=i+1;jn;j+) if(ri.key=rj.key)countj+; else counti+; 6、计数排序、计数排序(7)基数排序基数排序-多关键字排序多关键字排序例、扑克牌排序，规则：2 3 ka2 3 ka 23 ka 23 ka法：7、基数排序、基数排序-多关键字排序多关键字排序利用多关键码排序的思想处理单关键码的排序问题。假定有一个n个对象序列v0,v1,vn-1，且每个对象vi都含有d个关键码(ki1,ki2,kid

21、)。如果对于序列中任意两个对象vi和vj都满足：(ki1,ki2,kid)=(kj1,kj2,kjd)则称序列对关键码(k1,k2,kd)有序，其中， k1称为最高位关键码， kd称为最低位关键码。abab7、基数排序、基数排序-多关键字排序多关键字排序实现多关键码排序有两种常用的方法，一种是最高位优先法(msd,most significant digit first)，一种是最低位优先法(lsd,least significant digit first)。msd通常是一个递归过程：首先根据最高位关键码k1进行排序，得到若干个子序列，每个子序列中的对象都具有相同的关键码k1 。然后分别对每

22、个子序列根据关键码k2进行排序，按k2值的不同，再分成若干个更小的子序列，每个子序列中的对象具有相同的k1 、k2值。这样重复，直到对关键码kd完成排序为止。lsd做法是：首先根据最低关键码kd对所有对象进行一趟排序，然后根据次低关键码kd-1对上一趟排序结果再进行一次排序并保证排序结果对kd有序。这样重复，直到根据k1进行最后一趟排序为止。lsd也可以用于单关键码的排序，所要做的也可以用于单关键码的排序，所要做的是将单关键码分解成多关键码。是将单关键码分解成多关键码。算法思想算法思想：链式基数排序的过程就是d(是多关键码的个数)次分配和收集操作的过程。整个操作过程需要辅设多个队列，根据关键码

23、的取值范围确定辅设队列的个数。比如，对0-999之间的整数进行排序，每个数具有3个关键码，就是各数位上的数，每个关键码的取值范围都是0-9，因此需要设置10个队列。队列的用途是完成排序对象的分配与收集。这个10就是基数，他决定了队列的个数。7、基数排序、基数排序-多关键字排序多关键字排序链式基数排序链式基数排序7、基数排序、基数排序-多关键字排序多关键字排序链式基数排序链式基数排序614 738 921 485 637 101 215 530 790 306530 790 921 101 614 485 215 306 637 738第一次分配和收集第一次分配和收集790530101921 6

24、14306738 215485637 队列号队列号 0 1 2 3 4 5 6 7 8 97、基数排序、基数排序-多关键字排序多关键字排序链式基数排序链式基数排序101 306 614 215 921 530 637 738 485 790第二次分配和收集第二次分配和收集306101215614921 485738637530 790队列号队列号 0 1 2 3 4 5 6 7 8 9530 790 921 101 614 485 215 306 637 7387、基数排序、基数排序-多关键字排序多关键字排序链式基数排序链式基数排序101 215 306 485 530 614 637 738 790 921第三次分配和收集第三次分配和收集101 215485637614306530790738921队列号队列号 0 1 2 3 4 5 6 7 8 9101 306 614 215 921 530 637 738 485 790#define radix 26 /定义最大基数#define d 10 /定义关键字的位数void radixsort(rectype r, int d, int radix , int n)/*d是关键字的位数，radix是基数，n是待排序列的长度，r是静态链表结构，rectype包含next域*/ int hrad