内部排序1概述2插入排序3快速排序.ppt
数据结构 10.1 概述概述第十章第十章 内部排序内部排序 10.2 插入排序插入排序 10.3 快速排序快速排序 10.4 选择排序选择排序 10.5 归并排序归并排序 10.6 基数排序基数排序 10.7 各种内部排序方法的比较各种内部排序方法的比较 10.1 概述概述一一.排序的定义排序的定义 假设含有假设含有n n个记录的序列个记录的序列 r1,r2,rn,对应的对应的关键字序列为关键字序列为 k1,k2,kn,需确定一种关系需确定一种关系 p(1),p(2),p(n)使得关键字序列满足：使得关键字序列满足：kp1 kp2 kpn或者或者 kp1 kp2 kpn即使记录成为一个按关键字有序的序列即使记录成为一个按关键字有序的序列 rp1,rp2,rpn 这一过程称为排序。这一过程称为排序。二二.排序的稳定性排序的稳定性 在待排记录序列中，如果在待排记录序列中，如果任意任意两个关键字相两个关键字相同的记录，用某种排序方法排序后相对位置不变，同的记录，用某种排序方法排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的。则称这种排序方法是稳定的，否则称为不稳定的。设设 49,38,65,97,76,13,27,49,38,65,97,76,13,27,4949 是待排序列是待排序列 排序后排序后:13,27,38,49,:13,27,38,49,4949,65,76,97,65,76,97 稳定稳定 排序后排序后:13,27,38,:13,27,38,4949,49,65,76,97,49,65,76,97不稳定不稳定例例 10.1 概述概述排序稳定性的应用排序稳定性的应用股票交易系统股票交易系统：考虑一种股票交易：考虑一种股票交易 1 1）顾客输入：股东帐号、股票代码、申购价格、数量，）顾客输入：股东帐号、股票代码、申购价格、数量，股票交易系统将用户申购请求插入申购队列队尾；股票交易系统将用户申购请求插入申购队列队尾；2 2）股票交易系统按如下原则交易：）股票交易系统按如下原则交易：A A）申购价高者先成交）申购价高者先成交 B B）申购价相同者按申购时间先后顺序成交）申购价相同者按申购时间先后顺序成交例例申购队列：用线性表表示申购队列：用线性表表示交易前：将申购队列按申购价排序，显然为满足原则交易前：将申购队列按申购价排序，显然为满足原则 交易交易(B)(B)，要求排序方法是，要求排序方法是稳定稳定的的申购队列申购队列（09,10)09,10),(06,10.5),(033,9.8),(06,10.5),(033,9.8),(051,10)(051,10)排序后：排序后：(06,10.5),(06,10.5),(09,10)(09,10),(051,10)(051,10),(033,9.8),(033,9.8)实现实现 10.1 概述概述待排记录放于地址连续的存储单元中；待排记录放于地址连续的存储单元中；待排记录放于链表，记录之间的次序关系由待排记录放于链表，记录之间的次序关系由 指针指示。指针指示。待排记录存放在地址连续的存储单元中，同时待排记录存放在地址连续的存储单元中，同时另设一个指示各个记录存储位置的地址向量。另设一个指示各个记录存储位置的地址向量。三三.待排记录序列的存储方式待排记录序列的存储方式 10.1 概述概述四四.顺序存储结构表示待排记录顺序存储结构表示待排记录#define MAXSIZE 20 /顺序表的最大长度顺序表的最大长度typedef int KeyType;/定义关键字类型为整数类型定义关键字类型为整数类型typedef struct KeyType key;/关键字项关键字项 InfoType otherinfo;/其它数据项其它数据项RedType;/记录类型记录类型typedef struct RedType rMAXSIZE+1;/r0闲置或用作监视哨闲置或用作监视哨 int length;/顺序表长度顺序表长度SqList;/顺序表类型顺序表类型 10.1 概述概述 10.2 插入排序插入排序思路：思路：每步将一个待排序的对象，按其关键码大每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。位置上，直到对象全部插入为止。插入排序有多种具体实现算法：插入排序有多种具体实现算法：1)直接插入排序直接插入排序 2)希尔排序希尔排序一一.直接插入排序直接插入排序 10.2 插入排序插入排序思路：思路：将一个记录插入到已排好序的有序表中，将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增从而得到一个新的、记录数增1的有序表。的有序表。有序序列有序序列无序序列无序序列r r1r r2r ri-1r rir rnr ri+1r r1r r2r ri-1r rir rnr ri+1解决方法：解决方法：将第将第1个记录看成是初始有序表，然后从第个记录看成是初始有序表，然后从第2个记录起个记录起依次插入到这个有序表中，直到将第依次插入到这个有序表中，直到将第n个记录插入。个记录插入。关键问题关键问题(1)如何构造初始的有序序列？如何构造初始的有序序列？一一.直接插入排序直接插入排序 10.2 插入排序插入排序算法描述：算法描述：for(i=2;i=L.length;+i)关键问题关键问题(2)如何查找待插入记录的插入位置如何查找待插入记录的插入位置?解决方法：解决方法：在在i-1个记录的有序区个记录的有序区r1 ri-1中插入记录中插入记录ri，首，首先顺序查找先顺序查找ri的正确插入位置，然后将的正确插入位置，然后将ri插入到相插入到相应位置。应位置。一一.直接插入排序直接插入排序 10.2 插入排序插入排序算法描述：算法描述：L.r0=L.ri;for(j=i-1;L.r0.keyL.rj.key;-j)L.rj+1=L.rj;L.rj+1=L.r0;例例初始关键字初始关键字49 38 65 97 76 13 27 49()i=2i=238 49 65 97 76 13 27 49()(38)i=3i=338 49 65 97 76 13 27 49()(65)i=4i=438 49 65 97 76 13 27 49()(97)i=8i=813 27 38 49 49 65 76 97()(49)i=5i=538 49 65 76 97 13 27 49()(76)i=6i=613 38 49 65 76 97 27 49()(13)i=7i=713 27 38 49 65 76 97 49()(27)算法：算法：void InsertSort(SqList&L)for(i=2;i=L.length;+i)/只有一个元素也是有序表只有一个元素也是有序表 if(L.ri.keyL.ri-1.key)/只有只有“”才做插入操才做插入操作作 L.r0=L.ri;/r0为监视哨为监视哨 for(j=i-1;L.r0.keyL.rj.key;-j)L.rj+1=L.rj;/记录后移记录后移 L.rj+1=L.r0;/插入到正确位置插入到正确位置 void InsertSort(SqList&L)for(i=2;i=L.length;+i)/只有一个元素也是有序表只有一个元素也是有序表 if(L.ri.keyL.ri-1.key)/只有只有“”才做插入操作才做插入操作 L.r0=L.ri;/r0为监视哨为监视哨 for(j=i-1;L.r0.key=1&change;-i)change=FALSE;for(j=0;ji;+j)if(L.rj+1.keyL.rj.key)L.rjL.rj+1;change=TRUE;说明：起泡排序为稳定排序。说明：起泡排序为稳定排序。一一.起泡排序起泡排序 10.3 快速排序快速排序起泡排序的时间性能分析起泡排序的时间性能分析最好情况（正序）：最好情况（正序）：比较次数：比较次数：n-1移动次数：移动次数：0 1 12 23 34 45 5时间复杂度为时间复杂度为O(n)。1 12 23 34 45 5一一.起泡排序起泡排序 10.3 快速排序快速排序起泡排序的时间性能分析起泡排序的时间性能分析最好情况（正序）：最好情况（正序）：比较次数：比较次数：n-1移动次数：移动次数：0 时间复杂度为时间复杂度为O(n)。最坏情况（反序）：最坏情况（反序）：比较次数：比较次数：移动次数：移动次数：2)1(1-=nn(n-i)n-1i2)1(1-=n3n3(n-i)n-1i5 54 43 32 21 14 43 32 21 15 53 32 21 14 45 52 21 13 34 45 51 12 23 34 45 5平均情况：平均情况：时间复杂度为时间复杂度为O(n2)10.3 快速排序快速排序改进的着眼点：改进的着眼点：在起泡排序中，记录的比较和移动是在起泡排序中，记录的比较和移动是在在相邻相邻单元中进行的，记录每次交换只能上移或下移单元中进行的，记录每次交换只能上移或下移一个一个单元，因而总的比较次数和移动次数较多。单元，因而总的比较次数和移动次数较多。减少总的比较次数和移动次数减少总的比较次数和移动次数增大记录的比较和移动距离增大记录的比较和移动距离较大记录从前面直接移动到后面较大记录从前面直接移动到后面较小记录从后面直接移动到前面较小记录从后面直接移动到前面思路：思路：二二.快速排序快速排序 首先选一个首先选一个枢轴值枢轴值（即比较的基准），（即比较的基准），通过一趟通过一趟排序将待排记录排序将待排记录分割分割成独立的两部分，其中一部成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个分别对这两部分记录继续进行排序，以达到整个序列有序。序列有序。10.3 快速排序快速排序选择枢轴的方法：选择枢轴的方法：1.使用第一个记录的关键码；使用第一个记录的关键码；2.选取序列中间记录的关键码；选取序列中间记录的关键码；3.比较序列中第一个记录、最后一个记录和中间比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为枢轴并调换记录的关键码，取关键码居中的作为枢轴并调换到第一个记录的位置；到第一个记录的位置；4.随机选取枢轴。随机选取枢轴。选取不同枢轴的后果：选取不同枢轴的后果：决定两个子序列的长度，子序列的长度最好相等。决定两个子序列的长度，子序列的长度最好相等。10.3 快速排序快速排序 10.3 快速排序快速排序1313656527275050383849495555ji13133838656527275050494955551313656527275050494938385555jjiiijijjj 10.3 快速排序快速排序解决方法：解决方法：对分割得到的两个子序列递归地执行快速排序。对分割得到的两个子序列递归地执行快速排序。13132727383865655050494955551313272750503838494955556565ijij算法：算法：void Partition(SqList&L,int low,int high)L.r0=L.rlow;/用表的第一个记录作枢轴记录用表的第一个记录作枢轴记录 pivotkey=L.rlow.key;/枢轴记录关键字枢轴记录关键字 while(lowhigh)while(low=pivotkey)-high;L.rlow=L.rhigh;/比枢轴记录小的记录移到低端比枢轴记录小的记录移到低端 while(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;/比枢轴记录大的记录移到高端比枢轴记录大的记录移到高端 L.rlow=L.r0;return low;算法：算法：void QSort(SqList&L,int low,int high)/对顺序表的子表排序对顺序表的子表排序 if(lowhigh)/长度大于长度大于1 pivotloc=Partition(L,low,high);/枢轴位置枢轴位置 QSort(L,low,pivotloc-1);/对低子表递归排序对低子表递归排序 QSort(L.pivotloc+1,high);/对高子表递归排序对高子表递归排序 void QuickSort(SqList&L)/对顺序表排序对顺序表排序 QSort(L,1,L.length);例例初始关键字初始关键字 38 65 97 76 13 27 494949枢轴记录关键字枢轴记录关键字pivotkey=lowhighhigh27进行第一次进行第一次交换后交换后 27 38 65 97 76 13 49lowhighlow65进行第二次进行第二次交换后交换后 27 38 97 76 13 65 49lowhighhigh13进行第三次进行第三次交换后交换后 27 38 13 97 76 65 49lowhighlow97进行第四次进行第四次交换后交换后 27 38 13 76 97 65 49lowhighhighlowhigh例例初始关键字初始关键字 38 65 97 76 13 27 494949枢轴记录关键字枢轴记录关键字pivotkey=49进行第四次进行第四次交换后交换后 27 38 13 76 97 65 4949low=high完成一趟排序完成一趟排序 27 38 13 49 76 97 65 49 分别进行分别进行快速排序快速排序13 27 38 49 65 76 97 49 65 有序序列有序序列 13 27 38 49 49 65 76 97特点：特点：二二.快速排序快速排序 从时间上看，快速排序的平均性能优于前面所从时间上看，快速排序的平均性能优于前面所 讨论的各种排序方法。讨论的各种排序方法。快速排序为不稳定算法。快速排序为不稳定算法。如如：（3，2，2）排序后排序后：（2，2，3）10.3 快速排序快速排序练习练习 1.已知数据序列为已知数据序列为(12，5，9，20，6，31，24)，对该数据序列进行排序，写出直接插入排序、，对该数据序列进行排序，写出直接插入排序、起泡排序、快速排序每趟的结果。起泡排序、快速排序每趟的结果。2.设要将序列（设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母序的升序重新排列，则：中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是冒泡排序一趟扫描的结果是 ；初始步长为；初始步长为4的希尔排序一趟的结果是的希尔排序一趟的结果是 ；快速排序一趟扫；快速排序一趟扫描的结果是描的结果是 。
