数据结构 第八章教学课件 .ppt

数据结构 第八章教学课件 第八章 排序数据结构目录4123 基本概念插入排序交换排序选择排序5归并排序第八章第八章排序排序总体要求了解排序的定义和基本术语；掌握各种内部排序方法的基本思想、算法特点、排序过程以及它们的时间复杂度分析；了解稳定排序方法和不稳定排序方法的定义及判断。8.1 基本概念排序就是将一组任意序列的数据元素的按一定的规律进行排列，使之成为有序序列。假设含 n 个记录的序列为 R1,R2,Rn，其相应的关键字序列为 K1,K2,Kn 这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：Kp1Kp2Kpn 按此固有关系将上式记录序列重新排列为 Rp1,Rp2,Rpn 的操作称作排序排序。例：将关键字序列：52 49 80 36 14 58 61 23 调整为：14 23 36 49 52 58 61 80 设 Ki=Kj(1in,1jn,ij)，且在排序前的序列中 Ri 领先于 Rj（即 i j）。若在排序后的序列中 Ri 仍领先于 Rj，则称所用的排序方法是稳定的；反之，则称所用的排序方法是不稳定的。设排序前的关键字序列为：52,49,80,36,14,58,36,23 若排序后的关键字序列为：14,23,36,36,49,52,58,80，则排序方法是稳定的。若排序后的关键字序列为：14,23,36,36,49,52,58,80，则排序方法是不稳定的。内部排序和外部排序 若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的方法 逐步扩大记录的有序序列的过程 有序序列区 无 序 序 列 区有序序列区 无 序 序 列 区经过一趟排序 public class RecordTypeT extends Comparable T key;/关键字域/.其它域public RecordType()key=null;public RecordType(T data)key=data;本书把排序关键字假设为整数，并且用顺序表做存储结构。其数据结构定义为：public class SortT extends Comparable protected ArrayListRecordType elem;protected int length;/表长度public Sort(T data,int n)elem=new ArrayListRecordType();RecordType e;for(int i=0;in;i+)e=new RecordType(datai);elem.add(i,e);length=n;/各种排序方法8.2 插入排序u8.2.1直接插入排序初始状态 49 38 65 97 76 13 27 49 R0 R1 R2 R3 R4 R5 R6 R7i=1 i=2 38 49 65 97 76 13 27 49i=3 38 49 65 97 76 13 27 49i=4 38 49 65 76 97 13 27 49i=5 38 49 65 76 97 13 27 49i=6 38 49 65 76 97 13 27 49i=7 38 49 65 76 97 13 27 4949 38 65 97 76 13 27 49 49 38 排序过程：先将序列中第 1 个记录看成是一个有序子序列，然后从第 2 个记录开始，逐个进行插入，直至整个序列有序。【算法8-1】直接插入排序算法public void InsertSort(int n)int i,j;RecordType temp;for(i=1;i0&j-)temp=elem.get(j-1);elem.set(j-1,elem.get(j);elem.set(j,temp);elem.get(j-1)pareTo(elem.get(j).key)0T(n)=O(n)算法评价 时间复杂度：比较次数：最好的情况：待排序记录按关键字从小到大排列（正序）比较次数：最坏的情况：待排序记录按关键字从大到小排列（逆序）一般情况：待排序记录是随机的，取平均值。直接插入排序是稳定排序 u8.2.2希尔排序 思路：对待排序列先“宏观”调整，再“微观”调整 排序过程：先取一个正整数 d1 n，把所有相隔 d1 的记录放在一组内，组内进行直接插入排序；然后取 d2 d1，重复上述分组和排序操作；直至 di=1，即所有记录放进一个组中排序为止。其中 ddii 称为增量增量。第二趟希尔排序 第三趟分组，d3=1 第一趟希尔排序 第三趟希尔排序 第一趟分组，d1=5 第二趟分组，d2=3 R0 R1 R2 R3 R4 R5 R6 R7 R8 R949 38 65 97 76 13 27 49 55 04 49 38 65 97 76 13 27 49 55 04 13 27 49 55 04 49 38 65 97 76 13 27 49 55 04 49 38 65 97 76 13 04 49 38 27 49 55 65 97 76 04 13 27 38 49 49 55 65 76 970 1 2 3 4 5 6 7 8 9