数据结构第9章(排序)ppt课件.ppt

《数据结构第9章(排序)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索（查找）、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面数据结构第九章排序本章要点9.1基础知识9.2交换排序9.3插入排序9.4选择排序9.5归并排序9.6基数排序（删除，不讲）9.7各种排序方法的选择和使用本章小结9.1.1排序的概念【定义】假设含n个记录的序列为：{R1,R2,…，Rn}其相应的关键字序列为{K1,K2,…，Kn}这些关键字相互之间可以进行比较，即在它们之间

2、存在着这样一个关系Kp1≤Kp2≤…≤Kpn按此固有关系将的记录序列重新排列为{Rp1,Rp2,…，Rpn}的操作称作排序。【分类】1、增排序和减排序2、稳定排序和不稳定排序3、内部排序和外部排序9.1.2排序算法的效率分析1，时间复杂度评价标准：平均时间复杂度特例：对于那些受数据初始记录排列及记录数目影响比较大的算法，按最好情况和最坏情况分别估算2，空间复杂度评价标准：算法在执行过程中所需要的额外的存储空间。待排序的数据元素结构类型定义：为简单起见，假设关键字类型为整型。待排序的顺序表类型的类型定义如

3、下：typedefintKeyType//定义关键字类型typedefstructdataType//记录类型{keytypekey;//关键字项elemtypeotherelement;//其他数据项}RecType;本章要点9.1基础知识9.2交换排序9.3插入排序9.4选择排序9.5归并排序9.6基数排序（删除，不讲）9.7各种排序方法的选择和使用本章小结【交换排序思想】利用交换记录的位置进行排序的方法称为交换排序。其基本思想是：两两比较待排序记录的关键字，如果逆序就进行交换，直到所有记录都排好序

4、为止。常用的交换排序方法主要有冒泡排序和快速排序。快速排序是一种分区交换排序法，是对冒泡排序方法的改进。【例8-1】假设有8个记录，关键字分别为5013559727384965用冒泡排序方法排序。typedefintkeytype;voidBubbleSort(RecTypeR[],intn)//用冒泡排序对R[1]~R[n]记录排序{inti,j,flag=0;for(i=1;i

5、[j]=R[j+1];R[j+1]=R[0];}}}改进前的冒泡排序算法typedefintkeytype;voidBubbleSort(RecTypeR[],intn)//用冒泡排序对R[1]~R[n]记录排序{inti,j,flag=0;for(i=1;i

6、1];R[j+1]=R[0];}if(flag==1)return;//flag为True则表示序列已有序，可结束}}改进后的冒泡排序算法算法分析一，复杂度分析空间复杂度为O(1)。时间复杂度为O(n2)。二：稳定性稳定三：使用情况适用情况：n较小时（即带排序的数据元素较少时）改进思路1：双向起泡排序改进思路2：增大记录的比较和移动的位置改进思路快速排序（QuickSorting）又称分区交换排序，是对冒泡排序算法的改进，是一种基于分组进行互换的排序方法。【思想】：从待排记录序列中任取一个记录Ri作为基

7、准（通常取序列中的第一个记录），将所有记录分成两个序列分组，使排在Ri之前的序列分组的记录关键字都小于等于基准记录的关键字值Ri.key，排在Ri之后的序列分组的记录关键字都大于Ri.key，形成以Ri为分界的两个分组，此时基准记录Ri的位置就是它的最终排序位置。此趟排序称为第一趟快速排序。然后分别对两个序列分组重复上述过程，直到所有记录排在相应的位置上。【例8-2】假设有8个记录，关键字的初始序列为｛23,31,49,27,6,19｝，用快速排序法进行排序。需解决的关键问题：1，如何选择基准2，在待排

8、序记录中如何进行分区（通常叫做第一次划分）3，如何处理分区得到的两个待排序的子序列4，如何判断快速排序的结束1，取第一个记录的关键字2，取中间记录的关键字3，比较待排序记录中第一个记录，最后一个记录和中间一个记录的关键字，取中间值如何将小的记录移动到基准前面，将大的记录移动到基准后面？递归只剩一个记录为止假设有8个记录，关键字分别为5013559727384965用快速排序方法排序。课堂练习快速排序伪代码1，用left(i)和right（j