第八章 排序与查找.ppt

1、第八章 排序与查找,数据结构（C描述）,8.1 排序的基本概念,排序（Sorting） 对于有n个结点的线性表 ,按照节点某些数据项的关键字按递增或者递减的次序,重新排列线性表结点的过程称为排序 简单地说，排序就是把一组记录（元素）按照某个域的值的递增（即由小到大）或递减（即由大到小）的次序重新排列的过程。,排序码 : 作为排序依据的记录中的一个属性。它可以是任何一种可比的有序数据类型，它可以是记录的关键字，也可以是任何非关键字。 有序表与无序表: 一组记录按排序码的递增或递减次序排列得到的结果被称之为有序表，相应地，把排序前的状态称为无序表。,内排序与外排序: 按照排序过程中使用内外存的不同

2、将排序方法分为内排序和外排序。若排序过程全部在内存中进行，则称为内排序；若排序过程需要不断地进行内存和外存之间的数据交换，则称为外排序。内排序大致可分为五类：插入排序、交换排序、选择排序、归并排序和分配排序。本章仅讨论内排序。,为了以后讨论方便，我们直接将排序码写成一个一维数组的形式，具体类型设为Elemtype，并且在没有声明的情形下，所有排序都按排序码的值递增排列。,排序,插入排序（直插排序、二分排序、希尔排序）,交换排序（冒泡排序、快速排序）,选择排序 （直选排序、树型排序、堆排序）,归并排序（二路归并排序、多路归并排序）,分配排序 （多关键字排序、基数排序）,第二节 直接插入排序,直接

3、插入排序（Straight Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。,直接插入排序的算法实现,void insertsort(ElemType R,int n) /待排序元素用一个数组R表示，数组有n个元素 for ( int i=1; i=0) ,例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。它的直接插入排序的执行过程

4、如图9-1所示。,R0 R1 R2 R3 R4 R5,初始状态,(17 ) 3 25 14 20 9,第一次插入,(3 17 ) 25 14 20 9,第二次插入,(3 17 25 ) 14 20 9,第三次插入,(3 14 17 25 ) 20 9,第四次插入,(3 14 17 20 25 ) 9,第五次插入,(3 9 14 17 20 25),图,9,-,1,直接插入排序示例,第三节 二分插入排序,二分插入排序（Binary Insert Sort）的基本思想是：在有序表中采用二分查找的方法查找待排元素的插入位置。 其处理过程：先将第一个元素作为有序序列，进行n-1次插入，用二分查找的方法

5、查找待排元素的插入位置，将待排元素插入。,2二分插入排序的算法实现 其算法如下： void BinaryInsertSort(ElemType R,int n) for(int i=1; in; i+) /共进行n-1次插入 int left=0,right=i-1;ElemType temp=Ri; while(left=right) int middle=(left+right)/2; /取中点 if(tempRmiddle) right=middle-1; /取左区间,else left=middle+1; /取右区间 for(int j=i-1;j=left;j-) Rj+1=Rj;

6、/元素后移空出插入位 Rleft=temp; ,第四节 希尔排序,希尔排序（Shell Sort）又称为“缩小增量排序”。是1959年由D.L.Shell提出来的。该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。,例如，n=8，数组R的八个元素分别为：17，3，30，25，14，17，20，9。下面用图9-2给出希尔排序算法的执行过程。

7、,17,3,30,25,14,17,20,9,初始状态，,I,=4,14,3,17,9,20,17,30,25,第二趟结果，,I,=1,3,9,14,17,17,20,25,30,第三趟结果,14,3,20,9,17,17,30,25,第一趟结果，,I,=2,图,9,-,2,希尔排序算法的执行过程,第五节 冒泡排序,由于希尔排序对每个子序列单独比较，在比较时进行元素移动，有可能改变相同排序码元素的原始顺序，因此希尔排序是不稳定的。例如，给定排序码3，4，2，2，则希尔排序的结果变成2，2，3，4 。,冒泡排序（Bubble Sorting）的基本思想是：是通过对待排序序列从后向前（从下标较大的

8、元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部（从下标较大的单元移向下标较小的单元），就象水底下的气泡一样逐渐向上冒。,2冒泡排序的算法实现 void Bubblesort(ElemType R,int n) int flag=1; /当flag为0则停止排序 for (int i=1; i=i; j-),if (RjRj-1) ElemType t=Rj; /发生逆序 Rj=Rj-1; Rj-1=t;flag=1; /交换，并标记发生了交换 if(flag=0)return; ,例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，

9、9。下面用图9-3给出冒泡排序算法的执行过程。,图,9,-,3,冒泡排序示例,R0,R1,R2,R3,R4,R5,第一趟排序,3 (17 9 25 14 20),第二趟排序,3 9 (17 14 25 20),第三趟排序,3 9 14 (17 20 25),第,四趟排序,3 9 14 17 20 25,初始状态,（,17,3,25,14,20,9,),第六节 快速排序 1快速排序的基本思想,快速排序（Quick Sorting）是迄今为止所有内排序算法中速度最快的一种。它的基本思想是：任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元

10、素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面单元，排序码较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。,例如，给定排序码为：（46，55，13，42，94，05，17，70），具体划分如图9-4所示。,void quicksort(ElemType R,int left , int right) int i=left , j=right; ElemTy

11、pe temp=Ri; while (itemp) ,/一次划分得到基准值的正确位置 Ri=temp; if (lefti-1) quicksort(R,left,i-1); /递归调用左子区间 if (i+1right) quicksort(R,i+1,right); /递归调用右子区间,第七节 选择排序,直接选择排序,直接选择排序（straight select sorting）也是一种简单的排序方法。它的基本思想是：第一次从R0Rn-1中选取最小值，与R0交换，第二次从R1Rn-1中选取最小值，与R1交换，第三次从R2Rn-1中选取最小值，与R2交换，第i次从Ri-1Rn-1中选取最小值

12、，与Ri-1交换，, 第n-1次从Rn-2Rn-1中选取最小值，与Rn-2交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。,例如，给定n=8，数组R中的8个元素的排序码为：（8，3，2，1，7，4，6，5），则直接选择排序过程如图9-5所示。,第七节(二) 树形选择排序,从直接选择排序可知，在n个排序码中，找出最小值需n-1次比较，找出第二小值需n-2次比较，找出第三小值需n-3次比较，其余依此类推。所以，总的比较次数为：(n-1)+(n-2)+3+2+1= (n2-n)/2，那么，能否对直接选择排序算法加以改进，使总的比较次数比 (n2-n)/2小呢？显然，在n个排序码中选出

13、最小值，至少进行n-1次比较，但是，继续在剩下的n-1个关键字中选第二小的值，就并非一定要进行n-2次比较，若能利用前面n-1次比较所得信息，则可以减少以后各趟选择排序中所用的比较次数，,比如8个运动员中决出前三名，不需要7+6+5=18场比赛（前提是，若甲胜乙，而乙胜丙，则认为甲胜丙），最多需要11场比赛即可（通过7场比赛产生冠军后，第二名只能在输给冠军的三个对中产生，需 2场比赛，而第三名只能在输给亚军的三个对中产生，也需2场比赛，总共11场比赛）。具体见图9-6所示。,第八节 堆排序 堆的定义,若有n个元素的排序码k1，k2，k3，kn，当满足如下条件： kik2i kik2i （1）

14、kik2i+1 或 (2) kik2i+1 其中i=1,2,n/2 则称此n个元素的排序码k1，k2，k3，kn为一个堆。,若将此排序码按顺序组成一棵完全二叉树，则（1）称为小根堆（二叉树的所有根结点值小于或等于左右孩子的值），（2）称为大根堆（二叉树的所有根结点值大于或等于左右孩子的值）。,第九节 二路归并排序,二路归并排序的基本思想是：将两个有序子区间（有序表）合并成一个有序子区间，一次合并完成后，有序子区间的数目减少一半，而区间的长度增加一倍，当区间长度从1增加到n（元素个数）时，整个区间变为一个，则该区间中的有序序列即为我们所需的排序结果。,例如，给定排序码46，55，13，42，94

15、，05，17，70，二路归并排序过程如图9-10所示。,三趟归并：,05 13 17 42 46 55 70 94 ,二趟归并：,13 42 46 55 05 17 70 94 ,一趟归并：,46 55 13 42 05 94 17 70,初始状态：,46 55 13 42 94 05 17 70,图,9,-,10,二路归并排序过程示意图,各种内排序方法的比较 1从时间复杂度比较,从平均时间复杂度来考虑，直接插入排序、冒泡排序、直接选择排序是三种简单的排序方法，时间复杂度都为O(n2)，而快速排序、堆排序、二路归并排序的时间复杂度都为O(nlog2n)，希尔排序的复杂度介于这两者之间。若从最好

16、的时间复杂度考虑，则直接插入排序和冒泡排序的时间复杂度最好，为O(n)，其它的最好情形同平均情形相同。若从最坏的时间复杂度考虑，则快速排序的为O(n2)，直接插入排序、冒泡排序、希尔排序同平均情形相同，但系数大约增加一倍，所以运行速度将降低一半，最坏情形对直接选择排序、堆排序和归并排序影响不大。,2从空间复杂度比较 归并排序的空间复杂度最大，为O(n)，快速排序的空间复杂度为O(log2n)，其它排序的空间复杂度为O（1）。,3.从稳定性比较 直接插入排序、冒泡排序、归并排序是稳定的排序方法，而直接选择排序、希尔排序、快速排序、堆排序是不稳定的排序方法。,4从算法简单性比较 直接插入排序、冒泡

17、排序、直接选择排序都是简单的排序方法，算法简单，易于理解，而希尔排序、快速排序、堆排序、归并排序都是改进型的排序方法，算法比简单排序要复杂得多，也难于理解。,第十节 查找的基本概念,查找(searching) 就是在按某种数据结构形式存储的数据集合中,找出满足指定条件的节点 查找的分类 按查找的条件分类,可以分为按结点的关键码查找,关键码以外的其他数据项查找或其他数据项的组合查找等. 按查找的目的分类,可分为静态查找和动态查找.,静态查找 查找只是为了确定指定条件的结点存在与否 动态查找 查找是为了确定结点的插入位置或为了删除找到的结点 所谓关键字(key)是数据元素(或记录)中某个数据项的值

18、，用它可以标识(或识别)一个数据元素。,例如，描述一个考生的信息，可以包含：考号、姓名、性别、年龄、家庭住址、电话号码、成绩等关键字。 但有些关键字不能唯一标识一个数据元素，而有的关键字可以唯一标识一个数据元素。如刚才的考生信息中，姓名不能唯一标识一个数据元素(因有同名同姓的人)，而考号可以唯一标识一个数据元素(每个考生考号是唯一的，不能相同)。 我们将能唯一标识一个数据元素的关键字称为主关键字，而其它关键字称为辅助关键字或从关键字。,第十一节 顺序查找 顺序查找的基本思想,顺序查找是一种最简单的查找方法，它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值相比较

19、，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于的元素，则查找失败。,顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。,下面以顺序表的形式来描述算法。,2顺序查找算法实现,const int n=maxn /n为表的最大长度 struct node elemtype key; /key为关键字，类型设定为elemtype ;,int seqsearch (node Rn+1,elemtype k) /在表中查找关键字值为的元素 R0.key=k; int i=n; /从表

20、尾开始向前扫描 while(Ri.key!=k) i-; return i;,第十二节 二分查找,顺序查找的优点是算法简单，对表结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序或无序，它都同样适用。顺序查找的缺点是查找效率低，当n较大时，不宜采用顺序查找，而必须寻求更好的查找方法。 二分查找，也称折半查找，它是一种高效率的查找方法。但二分查找有条件限制：要求表必须用向量作存贮结构，且表中元素必须按关键字有序(升序或降序均可)。我们不妨假设表中元素为升序排列,二分查找的基本思想是：首先将待查值K与有序表R1到Rn的中点mid上的关键字Rmid.key进行比较，若相

21、等，则查找成功；否则，若Rmid.keyk ， 则在R1到Rmid-1中继续查找，若有Rmid.keyk ， 则在Rmid+1到Rn中继续查找。每通过一次关键字的比较，区间的长度就缩小一半，区间的个数就增加一倍，如此不断进行下去，直到找到关键字为K的元素；若当前的查找区间为空(表示查找失败)。,int binsearch (node Rn+1, elemtype k) int low=1, high=n; while (lowk) high=mid-1; /在左子区间中查找 else low=mid+1; /在右子区间中查找 return 0; /查找失败 ,第十三节 索引查找,索引查找，又称

22、分级查找，它既是一种查找方法，又是一种存贮方法，称为索引存贮。 它在我们的日常生活中有着广泛的应用。例如，在汉语字典中查找某个汉字时，若知道某个汉字读者，则可以先在音节表中查找到对应正文中的页码，然后再在正文中所对应的页中查出待查的汉字；在这里，整个字典就是索引查找的对象，字典的正文是字典的主要部分，被称之为主表，而检字表是为了方便查找主表而建立的索引，所以被称之为索引表。,第十四节 分块查找 1.分块查找 的思想,分块查找实际上就是一种索引查找，但查找的性能更优先于索引查找。原因是分块查找的索引表是一个有序表，故可以用二分查找 来代替 顺序查找 实现索引 表的快速查找。 具体实现如下：将一个

23、含有n个元素的主表分成m个子表，但要求子表之间元素是按关键字有序排列的，而子表中元素可以无序的，然后建立索引表，索引表中索引域的值用每个子表最大关键字代替，则可以按索引查找思想找到表中元素。,例如，给定关键字序列如下：18,7,26,34,15,42,36,70,60,55,83,90,78,72,74，假设m=3，s=5，即将该序序分成3个子表，每个子表有5 个元素，则得到的主表和索引表如图8-5所 示。,第十五节 散列查找,基本概念 散列查找，也称为哈希查找。它既是一种查找方法，又是一种存贮方法，称为散列存贮。散列存贮的内存存放形式也称为散列表。 散列查找，与前面介绍的查找方法完全不同，前

24、面介绍的所有查找都是基于待查关键字与表中元素进行比较而实现的查找方法，而散列查找是通过构造散列函数来得到待查关键字的地址，按理论分析真正不需要用到比较的一种查找方法。,例如，要找关键字为k的元素，则只需求出函数值H（k），H（k）为给定的散列函数，代表关键字k在存贮区中的地址，而存贮区为一块连续的内存单元，可用一个一维数组(或链表)来表示。,例8-4，假设有一批关键字序列18,75,60,43,54,90,46，给定散列函数H（k）=k%13，存贮区的内存地址从0到15，则可以得到每个关键字的散列地址为： H（18）=18%13=5 H（75）=75%13=10 H（60）=60%13=8 H

25、（43）=43%13=4,H（54）=54%13=2 H（90）=90%13=12 H（46）=46%13=7 于是，根据散列地址，可以将上述7个关键字序列存贮到一个一维数组HT（散列表）中，具体表示为：,其中HT就是散列存贮的表，称为散列表。从散列表中查找一个元素相当方便，例如，查找75，只需计算出H（75）=75%13=10，则可以在HT10中找到75。,上面讨论的散列表是一种理想的情形，即每一个关键字对应一个唯一的地址。但是有可能出现这样的情形，两个不同的关键字有可能对应同一个内存地址，即key1key2,而f(key1)=f(key2)。这样，将导致后放的关键字无法存贮，我们把这种现象

26、叫做冲突（collision）。 在散列存贮中，冲突是很难避免的，除非构造出的散列函数为线性函数。散列函数选得比较差，则发生冲突的可能性越大。我们把相互发生冲突的关键字互称为“同义词”。,散列函数的构造 散列函数的构造目标是使散列地址尽可能均匀地分布在散列空间上，同时使计算尽可能简单。具体常用的构造方法有如下几种：,1直接定址法 可表示为H（k）=a.k+b，其中a、b均为常数。 这种方法计算特别简单，并且不会发生冲突，但当关键字分布不连续时，会出现很多空闲单元，将造成大量存贮单元的浪费。,2数字分析法 对关键字序列进行分析，取那些位上数字变化多的、频率大的作为散列函数地址。,3平方取中法 取

27、关键字平方后的中间几位为散列函数地址。这是一种比较常用的散列函数构造方法，但在选定散列函数时不一定知道关键字的全部信息，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，因此，可以使用随机分布的关键字得到函数地址。,如图8-16中，随机给出一些关键字，并取平方后的第2到4位为函数地址。,在开放定址法中，解决冲突时具体使用下面一些方法。 （1）线性探查法,假设散列表的地址为0m-1，则散列表的长度为m。若一个关键字在地址d处发生冲突，则依次探查d+1，d+2，m-1(当达到表尾m-1时，又从0，1，2，.开始探查)等地址，直到找到一个空闲位置来装冲突处的关键字，将这一种方法称为线性探查法。假设发生冲突时的地址为d0=H(k)，则探查下一位置的公式为di=(di-1+1)%m (1im-1)，最后将冲突位置的关键字存入di地址中。,例8-5 给定关键字序列为19，14，23，1，68，20，84，27，55，11，10，79，散到函数H（k）=k%13 ，散列表空间地址为012，试用线性探查法建立散列存贮(散列表)结构。 得到的散列表如图8-17所示,(2) 平方探查法 该方法规定，若在d地址发生冲突，下一次探查位置为d+12，d+22，直到找到一个空闲位置为止。,(3) 双散列函数探查法 该方