内部排序1概述2插入排序3快速排序.ppt

《内部排序1概述2插入排序3快速排序.ppt》由会员分享，可在线阅读，更多相关《内部排序1概述2插入排序3快速排序.ppt（38页珍藏版）》请在三一办公上搜索。

1、数据结构,10.1 概述,第十章 内部排序,10.2 插入排序,10.3 快速排序,10.4 选择排序,10.5 归并排序,10.6 基数排序,10.7 各种内部排序方法的比较,10.1 概述,一.排序的定义,二.排序的稳定性,在待排记录序列中，如果任意两个关键字相同的记录，用某种排序方法排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的。,10.1 概述,排序稳定性的应用,股票交易系统：考虑一种股票交易 1）顾客输入：股东帐号、股票代码、申购价格、数量，股票交易系统将用户申购请求插入申购队列队尾；2）股票交易系统按如下原则交易：A）申购价高者先成交 B）申购价相同者按申购时间先后

2、顺序成交,例,10.1 概述,待排记录放于地址连续的存储单元中；待排记录放于链表，记录之间的次序关系由 指针指示。待排记录存放在地址连续的存储单元中，同时另设一个指示各个记录存储位置的地址向量。,三.待排记录序列的存储方式,10.1 概述,四.顺序存储结构表示待排记录,#define MAXSIZE 20/顺序表的最大长度typedef int KeyType;/定义关键字类型为整数类型typedef struct KeyType key;/关键字项 InfoType otherinfo;/其它数据项RedType;/记录类型typedef struct RedType rMAXSIZE+1;

3、/r0闲置或用作监视哨 int length;/顺序表长度SqList;/顺序表类型,10.1 概述,10.2 插入排序,思路：,每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。,插入排序有多种具体实现算法：1)直接插入排序 2)希尔排序,一.直接插入排序,10.2 插入排序,思路：,将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。,解决方法：将第1个记录看成是初始有序表，然后从第2个记录起依次插入到这个有序表中，直到将第n个记录插入。,关键问题(1)如何构造初始的有序序列？,一.直接插入排序,10.2 插入排

4、序,算法描述：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,(),算法：,void InsertSort(SqList/插入到正确位置,void InsertSort(SqList/插入到正

5、确位置,38 49 65 76 97 13 27 49,(),j,一.直接插入排序,10.2 插入排序,算法分析,最好情况（正序）,最坏情况（逆序）,时间复杂度为 O(n2),二.希尔排序（缩小增量排序）,若待排序记录按关键码基本有序时，直接插入 排序的效率可以大大提高；由于直接插入排序算法简单，则在待排序记录 数量n较小时效率也很高。,改进：,10.2 插入排序,二.希尔排序（缩小增量排序）,先将整个待排记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。,思路：,10.2 插入排序,基本有序指已接近正序：1,2,8,4,5,6,

6、7,3,9局部有序指某些部分有序：6,7,8,9,1,2,3,4,5,二.希尔排序（缩小增量排序）,问题1：如何使待排记录个数较少；问题2：如何分割待排序列；问题3：子序列内如何进行直接插入排序。,待解决问题：,10.2 插入排序,例,初始关键字,49 38 65 97 76 13 27 49,增量序列的最后一个增量必须为1。希尔排序较直接插入排序时间复杂度低,时间 性能在O(n2)和O(nlog2n)之间。算法不稳定。如2,5,5,4。,说明：,二.希尔排序（缩小增量排序）,10.2 插入排序,思路：,快速排序有多种具体实现算法：1)起泡排序 2)快速排序,10.3 快速排序,在待排序列中选

7、两个记录，将它们的关键码相比较，如果反序（即排列顺序与排序后的次序正好相反），则交换它们的存储位置。,思路：,一.起泡排序,对相邻记录关键字进行比较，若为逆序，则交换两记录。然后依次进行第n-1个记录和第n个记录关键字的比较。此过程称为第一趟排序。一般情况下，整个起泡排序只需进行k(1kn)趟操作，起泡排序的结束条件是“在某一趟排序过程中没有进行记录交换的操作”。,10.3 快速排序,例,一.起泡排序,4938659776132749,38 4965761327 49 97,初始关键字,第一趟排序后,49,38,3849659776132749,49,65,3849659776132749,6

8、5,97,3849659776132749,97,76,3849657697132749,97,13,3849657613972749,97,27,3849657613279749,97,49,例,一.起泡排序,4938659776132749,38 4965761327 49 97,38 4965132749 76 97,38 491327 49 65 76 97,38 1327 49 49 65 76 97,3813 27 49 49 65 76 97,13 27 38 49 49 65 76 97,初始关键字,第一趟排序后,第二趟排序后,第三趟排序后,第四趟排序后,第五趟排序后,第六趟排

9、序后,算法：,void Bubble_Sort(SqList,说明：起泡排序为稳定排序。,一.起泡排序,10.3 快速排序,起泡排序的时间性能分析,最好情况（正序）：,时间复杂度为O(n)。,一.起泡排序,10.3 快速排序,起泡排序的时间性能分析,最好情况（正序）：,时间复杂度为O(n)。,最坏情况（反序）：,平均情况：时间复杂度为O(n2),10.3 快速排序,改进的着眼点：在起泡排序中，记录的比较和移动是在相邻单元中进行的，记录每次交换只能上移或下移一个单元，因而总的比较次数和移动次数较多。,减少总的比较次数和移动次数,增大记录的比较和移动距离,较大记录从前面直接移动到后面较小记录从后面

10、直接移动到前面,思路：,二.快速排序,首先选一个枢轴值（即比较的基准），通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。,10.3 快速排序,选择枢轴的方法：1.使用第一个记录的关键码；2.选取序列中间记录的关键码；3.比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为枢轴并调换到第一个记录的位置；4.随机选取枢轴。,关键问题：如何选择枢轴？,选取不同枢轴的后果：决定两个子序列的长度，子序列的长度最好相等。,10.3 快速排序,关键问题：如何进行一次划分？,10.3 快速排序,

11、13,65,27,50,38,49,55,关键问题:如何处理分割得到的两个待排序子序列？,10.3 快速排序,解决方法：对分割得到的两个子序列递归地执行快速排序。,38,算法：,void Partition(SqList,算法：,void QSort(SqList/对高子表递归排序,void QuickSort(SqList,例,初始关键字,38 65 97 76 13 27 49,49,49,枢轴记录关键字pivotkey=,low,high,27,65,13,97,例,初始关键字,38 65 97 76 13 27 49,49,49,枢轴记录关键字pivotkey=,49,进行第四次交换后,27 38 13 76 97 65 49,49,low=high,特点：,二.快速排序,从时间上看，快速排序的平均性能优于前面所 讨论的各种排序方法。快速排序为不稳定算法。如：（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的希尔排序一趟的结果是；快速排序一趟扫描的结果是。,