欢迎来到天天文库
浏览记录
ID:59941456
大小:1.55 MB
页数:63页
时间:2020-11-28
《零基础学数据结构-第12章-内排序教学提纲.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、零基础学数据结构-第12章-内排序12.1基本概念稳定排序和不稳定排序:在待排序的记录序列中,若存在两个或两个以上关键字想到呢个的记录。假设ki=kj(1≤i≤n,1≤j≤n,i≠j),且排序前的对应的记录Ei领先于Ej(即i2、:由于待排序的记录数量不同,使得排序过程中涉及的存储器不同,可将排序方法分为两类:内部排序和外部排序。内部排序也称为内排序,指的是待排序记录存放在计算机随机存储器中进行的排序过程;外部排序也称为外排序,指的是待排序记录的数据流很大,以致内存一次不能容纳全部记录,在排序的过程中需要不断对外存进行访问的排序过程。12.1基本概念内排序的方法有许多,按照排序过程中采用的策略将排序分为几个大类:插入排序、选择排序、交换排序和归并排序。在排序过程中,需要以下两种基本操作:(1)比较两个元素相应关键字的大小;(2)将元素从一个位置移动到另一个3、位置。其中,第(1)种操作对大多数排序方法来说都是必要的,第(2)种操作可通过改变记录的存储方式可以避免。12.1基本概念待排序的记录序列可有下列3种存储方式:(1)顺序存储。待排序的元素存储在一组连续的存储单元中,这类似于线性表的顺序存储,在序列中相邻的两个记录Ei和Ej,它们的物理位置也相邻。在这种存储方式中,记录之间的次序关系由其存储位置决定,则实现排序必须要移动记录。(2)链式存储。待排序元素存储在一组不连续的存储单元中,这类似于线性表的链式存储,序列中相邻的两个记录Ei和Ej,其物理位置不一定相邻。在这种存储方式中,记录4、之间的关系由附设的指针指示,在进行排序时,不需要移动元素,只需要修改指针即可。(3)静态链表。带排序记录存放在静态链表中,记录之间的关系由被称为游标的指针指示,实现排序不需要移动元素,只需要修改游标即可。12.2插入排序12.2.1直接插入排序直接插入排序(straightinsertionsort)是一种最简单的插入排序算法。它的基本算法思想描述如下:假设待排序元素有n个,初始时,已排序子集只有一个元素,即第1个元素。未排序子集是剩下的n-1个元素。例如,有4个待排序元素22、6、17和8,排序前的状态如图12.1所示。12.25、插入排序第1趟排序:将无序集中的第一个元素,也就是6与有序集中的元素22进行比较,因为22>6,所以需要先将22向后移动一个位置,然后将6插入到第一个位置,如图12.2所示。其中,阴影部分表示无序集,白色部分表示有序集。第2趟排序:将无序集的元素17从右到左依次与有序集中的元素比较,即先与22比较,因为17<22,所以先将22向后移动一个位置,然后比较17与第1个元素6的大小,因为17>6,所以将17放在第2个元素的位置,如图12.3所示。12.2插入排序第3趟排序:将待排序集合中的元素8与已经有序的元素集合从右到左依次比较,先与6、22比较。因为8<22,所以需要将22向后移动一个位置并与前一个元素17比较。由于8<17,将17向后移动并继续与6进行比较。因为8>6,所以将8放在第2个位置,如图12.4所示。12.2插入排序假设待排序元素有8个,分别是17、46、32、87、58、9、50、38。使用直接插入排序对该元素序列的排序过程如图12.5所示。12.2插入排序直接插入排序算法描述如下。voidInsertSort(SqList*L)/*直接插入排序*/{inti,j;DataTypet;for(i=1;ilength;i++)/*前i个元素已7、经有序,从第i+1个元素开始与前i个有序的关键字比较*/{t=L->data[i+1];/*取出第i+1个元素,即待排序的元素*/j=i;while(j>0&&t.keydata[j].key)/*寻找当前元素的合适位置*/{L->data[j+1]=L->data[j];j--;}L->data[j+1]=t;/*将当前元素插入合适的位置*/}}12.2插入排序12.2.2折半插入排序折半插入排序算法是直接插入排序的改进。它的主要改进在于,在已经有序的集合中使用折半查找法确定待排序元素的插入位置。在找到要插入的位置后,将8、待排序元素插入到相应的位置。假设待排序元素有7个:67、53、73、21、34、98、12。使用折半插入排序对该元素序列第一趟排序过程如图12.6所示。12.2插入排序第2趟折半插入排序过程如图12.7所示。12.2插入排序voidBinInser
2、:由于待排序的记录数量不同,使得排序过程中涉及的存储器不同,可将排序方法分为两类:内部排序和外部排序。内部排序也称为内排序,指的是待排序记录存放在计算机随机存储器中进行的排序过程;外部排序也称为外排序,指的是待排序记录的数据流很大,以致内存一次不能容纳全部记录,在排序的过程中需要不断对外存进行访问的排序过程。12.1基本概念内排序的方法有许多,按照排序过程中采用的策略将排序分为几个大类:插入排序、选择排序、交换排序和归并排序。在排序过程中,需要以下两种基本操作:(1)比较两个元素相应关键字的大小;(2)将元素从一个位置移动到另一个
3、位置。其中,第(1)种操作对大多数排序方法来说都是必要的,第(2)种操作可通过改变记录的存储方式可以避免。12.1基本概念待排序的记录序列可有下列3种存储方式:(1)顺序存储。待排序的元素存储在一组连续的存储单元中,这类似于线性表的顺序存储,在序列中相邻的两个记录Ei和Ej,它们的物理位置也相邻。在这种存储方式中,记录之间的次序关系由其存储位置决定,则实现排序必须要移动记录。(2)链式存储。待排序元素存储在一组不连续的存储单元中,这类似于线性表的链式存储,序列中相邻的两个记录Ei和Ej,其物理位置不一定相邻。在这种存储方式中,记录
4、之间的关系由附设的指针指示,在进行排序时,不需要移动元素,只需要修改指针即可。(3)静态链表。带排序记录存放在静态链表中,记录之间的关系由被称为游标的指针指示,实现排序不需要移动元素,只需要修改游标即可。12.2插入排序12.2.1直接插入排序直接插入排序(straightinsertionsort)是一种最简单的插入排序算法。它的基本算法思想描述如下:假设待排序元素有n个,初始时,已排序子集只有一个元素,即第1个元素。未排序子集是剩下的n-1个元素。例如,有4个待排序元素22、6、17和8,排序前的状态如图12.1所示。12.2
5、插入排序第1趟排序:将无序集中的第一个元素,也就是6与有序集中的元素22进行比较,因为22>6,所以需要先将22向后移动一个位置,然后将6插入到第一个位置,如图12.2所示。其中,阴影部分表示无序集,白色部分表示有序集。第2趟排序:将无序集的元素17从右到左依次与有序集中的元素比较,即先与22比较,因为17<22,所以先将22向后移动一个位置,然后比较17与第1个元素6的大小,因为17>6,所以将17放在第2个元素的位置,如图12.3所示。12.2插入排序第3趟排序:将待排序集合中的元素8与已经有序的元素集合从右到左依次比较,先与
6、22比较。因为8<22,所以需要将22向后移动一个位置并与前一个元素17比较。由于8<17,将17向后移动并继续与6进行比较。因为8>6,所以将8放在第2个位置,如图12.4所示。12.2插入排序假设待排序元素有8个,分别是17、46、32、87、58、9、50、38。使用直接插入排序对该元素序列的排序过程如图12.5所示。12.2插入排序直接插入排序算法描述如下。voidInsertSort(SqList*L)/*直接插入排序*/{inti,j;DataTypet;for(i=1;ilength;i++)/*前i个元素已
7、经有序,从第i+1个元素开始与前i个有序的关键字比较*/{t=L->data[i+1];/*取出第i+1个元素,即待排序的元素*/j=i;while(j>0&&t.keydata[j].key)/*寻找当前元素的合适位置*/{L->data[j+1]=L->data[j];j--;}L->data[j+1]=t;/*将当前元素插入合适的位置*/}}12.2插入排序12.2.2折半插入排序折半插入排序算法是直接插入排序的改进。它的主要改进在于,在已经有序的集合中使用折半查找法确定待排序元素的插入位置。在找到要插入的位置后,将
8、待排序元素插入到相应的位置。假设待排序元素有7个:67、53、73、21、34、98、12。使用折半插入排序对该元素序列第一趟排序过程如图12.6所示。12.2插入排序第2趟折半插入排序过程如图12.7所示。12.2插入排序voidBinInser
此文档下载收益归作者所有