数据结构课件-排序.ppt

1、第第1010章章 排序排序一、基本概念一、基本概念l排序排序：将文件中的记录按照关键字值关键字值递增或递减的顺序排列起来。l排序的稳定与不稳定排序的稳定与不稳定：若关键字相同的记录在排序后先后顺序仍然不变，则称所用的排序方法是稳定的，否则就是不稳定的。l内部排序内部排序：全部在内存中进行的排序l外部排序外部排序：排序中需使用内存与外存内部排序：内部排序：插入排序，交换排序，选择排序，归并排序，基数排序等。内部排序与存储结构：（1）一维数组作为存储结构：对记录进行物理重排；（2）以链表作为存储结构：无须移动记录，仅需修改指针即可；（3）建立索引表辅助排序排序算法的评价标准：排序算法的评价标准：（

2、1）时间；（2）执行算法所需的附加空间；（3）算法复杂度。主要是时间代价：主要是时间代价：算法的比较次数和移动次数。注：简单的排序方法，时间复杂度O(n2);先进的排序方法，时间复杂度O(nlogn)；基数排序，时间复杂度O(dn)。以数组作为文件的存储结构#define MAXSIZE 100 typedef struct KeyType key;InfoType otherinfo;RecType;typedef struct RecType rMAXSIZE+1;/r0闲置或作为哨兵单元 int length;SqList;如：以某课程考试成绩为关键字的排序二、二、插入排序插入排序(In

3、sertion Sort)(Insertion Sort)定义：定义：将待排序记录分为有序区和无序区，每次将无序区中的第一个记录按其关键字值的大小插入到有序区中的适当位置，直到无序区记录全部插入为止。1 1 直接插入排序直接插入排序方法方法：在插入第i个记录时，R1,R2,，Ri-1已排好序，将关键字ki依次与关键字ki-1,ki-2,k1进行比较，从而找到应该插入的位置，然后将记录Ri插入。对R1Rn进行排序，R0为监视哨 47 33 61 82 72 11 25 47 47 33 61 82 72 11 25 47 33 33 47 61 82 72 11 25 47 /334733 33

4、 47 61 82 72 11 25 4733 33 47 61 82 72 11 25 4772 33 47 61 72 82 11 25 4711 33 47 61 72 8282 25 47 /1182 11 33 47 61 7272 82 25 47 /117211 33 47 6161 72 82 25 47 /1161 11 33 4747 61 72 82 25 47 /114711 3333 47 61 72 82 25 47 /113311 11 33 47 61 72 82 25 47 /结束11的插入排序25 11 25 33 47 61 72 82 47 /47 11

5、 25 33 47 47 61 72 82 中间过程中间过程算法：void InsertSort(SqList&L)for(i=2;i=L.length;i+)if(L.ri.keyL.ri-1.key)/需将L.ri插入有序子表 L.r0=L.ri;L.ri=L.ri-1;for(j=i-2;L.r0.keyL.rj.key;j-)L.rj+1=L.rj;/记录后移 L.rj+1=L.r0;/插入到正确位置 时间复杂度O(n2)，稳定2 2、希尔排序希尔排序（ShellShells methods method）“缩小增量排序”(Diminishing Increment Sort)基本思想

6、基本思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。步骤步骤：1.对整个待排记录序列，按间隔d1分组，组内排序2.取d2 0 m0）、）、R Ri+di+d*m m(i+d(i+d*m=n)m=n)同组同组void ShellInsert(SqList&L,int dk)for(i=dk+1;i=L.length;i+)if(L.ri.key0&L.r0.keyL.rj.key;j-=dk)L.rj+dk=L.rj;/记录后移 L.rj+dk=L.r0;/插入到正确位置 void ShellSort(SqLi

7、st&L,int d,int t)/d为增量序列数组，t为增量数 for(k=0;k147 33 61 82 72 11若中间数介于47 和11之间，必然减少逆转数不稳定三、三、选择排序选择排序（Selection SortSelection Sort）基本思想基本思想：每一趟在待排序的记录中选出关键字最小的记录，依次放在已排序的记录序列的最后，直至全部记录排完为止。1.1.简单选择排序简单选择排序 第一趟排序：在无序区R1Rn中选出关键字最小的记录，将它与R1交换；第二趟排序：在无序区R2Rn中选出关键字最小的记录，将它与R2交换；第i趟排序：R1Ri-1已是有序区，在当前无序区RiRn中选

8、出关键字最小的记录Rk，将它与Ri交换；进行n-1趟排序后，整个文件就是递增有序的。49 38 65 97 76 13 27 4913 38 65 97 76 49 27 4913 27 65 97 76 49 38 4913 27 38 97 76 49 65 4913 27 38 49 76 97 65 4913 27 38 49 49 97 65 7613 27 38 49 49 65 97 7613 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97 算法流程：1 for i=1 to n-12 j=i3 for k=i+1 to n4 if(Rj

9、Rk)then j=k5 end(k)6 if(ji)then ri与rj互换7 End(i)8 return void SelectSort(SqList&L)int i,j,k;RecType temp;for(i=1;iL.length;i+)j=i;for(k=i+1;kL.rk.key)j=k;if(j i)temp=L.ri;L.ri=L.rj;L.rj=temp;时间复杂度O(n2)，稳定堆：n个元素的序列k1,k2,kn，当且仅当满足以下关系时，称之为堆。时间复杂度O(nlogn)，不稳定把堆看作一棵完全二叉树，所有非终端结点的值均不大于（或不少于）其左右孩子结点的值。堆顶元素

10、是堆序列的最小值（最大值）堆排序：输出堆顶最小值（最大值）后，使得剩余的元素序列重又建成一个堆，得到次小值（次大值）。如此反复执行得到一个有序序列的过程。堆排序步骤：1.从无序序列构建初始堆 2.反复筛选输出有序序列 第1步其实也是一个反复筛选的过程，因此筛选是堆排序的关键 筛选过程 构建初始堆 四、四、交换排序交换排序基本思想基本思想：两两比较待排序记录的关键字，发现两个记录逆序时即进行交换，直至没有逆序的记录为止。1 1 起泡排序起泡排序（Bubble methodBubble method）基本思想基本思想：通过对相邻关键字的比较和交换，使全部记录排列有序。过程过程：每两个相邻的关键字进

11、行比较，若为逆序，则将两记录交换位置，反复进行这一操作。如此一趟排序后，可将关键字最大的记录安排在最后一个记录的位置上，然后对前n-1个记录重复同样操作，再将次小关键字安排再倒数第二个记录的位置上。重复进行，直至某一趟没有记录交换完成排序。473361827211254733476172112547823347611125477282334711254761728233112547476172821125334747617282112533474761728211253347476172821125334747617282设置指示变量，以判断每次扫描时是否有记录交换 void BubbleSo

12、rt(SqList&L)int i,j,flag;RecType temp;for(i=L.length;i1;i-)flag=TRUE;for(j=1;jL.rj+1.key)temp=L.rj+1;L.rj+1=L.rj;L.rj=temp;flag=FALSE;if(flag)break;时间复杂度O(n2)，稳定2 2 快速排序快速排序（Quick SortQuick Sort）基本思想基本思想：通过一趟排序将原有记录分成两部分，然后分别对这两部分进行排序以达到最后所有记录有序。即在当前无序子区R1Rh中任取一个记录作为比较的基准，用此基准将当前无序区划分为左右两个较小的无序子区：R1

13、Ri-1和Ri+1Rh，左边无序子区记录关键字均小于或等于基准关键字，右边则大于或等于基准关键字。反复进行，直至无序子区记录已排好序为止。对当前无序子区对当前无序子区R1RhR1Rh进行划分的方法：进行划分的方法：设置两个指示器i和j，它们的初值分别为：i=1,j=h。设基准temp为无序子区中的第一个记录Ri(即R1)。将j自h起向左扫描，直至找到第一个关键字小于temp.key的记录Rj，将Rj移至i所指的位置上；然后，令i自i+1起向右扫描，直至找到第一个关键字大于temp.key的记录Ri，将Ri移至j所指的位置上；接着令j自j-1起向左扫描，如此交替改变扫描方向，从两端各自往中间靠拢

14、，直至i=j时，i便是基准x的最终位置，将x放在此位置上就完成了一次划分。O(nlogn)，不稳定49 38 65 97 76 13 27 49ij49 38 65 97 76 13 27 49ij27 38 65 97 76 13 49 49ij27 38 65 97 76 13 49 49ij27 38 49 97 76 13 65 49ij49 38 65 97 76 13 27 49ij49 38 65 97 76 13 27 49ij27 38 65 97 76 13 49ij27 38 65 97 76 13 49ij27 38 97 76 13 65 49ij/一趟快速排序int

15、 partition(SqList&L,int low,int high)L.r0=L.rlow;pivotkey=L.rlow.key;while(low high)while(low=pivotkey)-high;L.rlow=L.rhigh;while(low high&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;L.rlow=L.r0;return low;/快速排序void QSort(SqList&L,int low,int high)if(low 红红 梅梅 方，然后是点数，按方，然后是点数，按1313个点数个点数 的自然数顺序排序，另外假设花色优先级比点数高的自然数顺序排序，另外假设花色优先级比点数高 排序有两种方式：排序有两种方式：1.1.先花色，再点数（最高位优先先花色，再点数（最高位优先MSDMSD）2.2.先点数，再花色（最低位优先先点数，再花色（最低位优先LSDLSD）链式基数排序是借助分配和收集两种操作使用链表作链式基数排序是借助分配和收集两种操作使用链表作为组织结构对单逻辑关键字进行排序的方法。为组织结构对单逻辑关键字进行排序的方法。本节重点：本节重点：1 各种排序算法的原理与实现2 各种排序算法特点及相互比较任选2种排序算法，对单链表元素进行现场排序。引入“三者取中”，“冒泡排序”对快速排序算法进行改进