零基础学数据结构-第12章-内排序教学提纲.ppt

《零基础学数据结构-第12章-内排序教学提纲.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、零基础学数据结构-第12章-内排序12.1基本概念稳定排序和不稳定排序：在待排序的记录序列中，若存在两个或两个以上关键字想到呢个的记录。假设ki=kj(1≤i≤n,1≤j≤n,i≠j)，且排序前的对应的记录Ei领先于Ej（即i

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