查找与排序软件基础知识.ppt
第三章 查找与排序,1 基本的查找技术2 基本的排序技术3 二叉排序树及其查找,3.1基本的查找技术,顺序查找有序表的对分查找,顺序查找,(1)如果线性表为无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。(2)即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。,线性表在顺序存储结构下的顺序查找输入：线性表长度n以及线性表的存储空间V；被查找的元素x。输出：被查找元素x在线性表中的序号k。如果在线性表中不存在元素x，则输出k1。,int serch(int v，int n，int x)int k；k0；while(kn)&(vkx)kk1；if(kn)k1；return(k)；,3.1.2 有序表的对分查找,设有序线性表的长度为n，被查元素为x。将x与线性表的中间项进行比较：若中间项的值等于x，则说明查到，查找结束；若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0(说明线性表中没有这个元素)为止。在最坏情况下，对分查找只需比较log2n次，而顺序查找需比较n次。,有序线性表在顺序存储结构下的对分查找,输入：有序线性表长度n以及线性表的存储空间V；被查找的元素x。输出：被查找元素x在有序线性表中的序号k。如果在线性表中不存 在元素x，则输出k1。,int bserch(int v，int n，int x)int i，j，k；i1；jn；while(ij)k(ij)/2；if(vk1x)return(k1)；if(vk1x)jk1；else ik1；return(1)；,3.2 基本排序技术,交换排序（冒泡排序与快速排序）插入排序（简单插入排序与希尔排序）选择排序（简单选择排序与堆排序）,排序的一些基本概念,简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来（递增或递减）。,数据表(Data List)待排序的数据对象的有限集合。关键字(Key)作为排序依据的数据对象中的属性域。主关键字 不同的数据对象若关键字互不相同，则这种关键字称为主关键字。排序的确切定义 使一组任意排列的对象变成一组按关键字线性有序的对象。,排序的时间开销 它是衡量算法好坏的最重要的标志。通常用算法执行中的数据比较次数和数据移动次数来衡量。,一 交换排序,基本原理：两两比较待排序的对象的关键字，如果发生逆序，则交换之，直到全部对象都排好序为止。,两种常见的交换排序冒泡排序(Bubble Sort)快速排序(Quick Sort),冒泡排序的基本过程,1.假设待排序的n个对象的序列为V0,V1,.,Vn-1，起始时排序范围是从V0到Vn-12.在当前的排序范围之内，自右至左对相邻的两个结点依次进行比较，让值较大的结点往下移(下沉)，让值较小的结点往上移(上冒)。每趟起泡都能保证值最小的结点上移至最左边，下一遍的排序范围为从下一结点到Vn-1。3.在整个排序过程中，最多执行(n-1)遍。但执行的遍数可能少于(n-1)，这是因为在执行某一遍的各次比较没有出现结点交换时，就不用进行下一遍的比较,冒泡排序示例,i(0)(1)(2)(3)(4)(5)21 25 49 25*16 08 1 08 21 25 49 25*16 2 08 16 21 25 49 25*3 08 16 21 25 25*49 4 08 16 21 25 25*49,冒泡排序算法void bubblesort(int R,int n)int i,j,flag;int temp;for(i=0;i=i;j-)if(Rj+1Rj)temp=Rj+1;Rj+1=Rj;Rj=temp;flag=0;if(flag)break;,起泡排序的时间复杂度,考虑关键字的比较次数和对象移动次数1、在最好情况下，初始状态是递增有序的，一趟扫描就可完成排序，关键字的比较次数为n-1，没有记录移动。2、若初始状态是反序的，则需要进行n-1趟扫描，每趟扫描要进行n-i次关键字的比较，且每次需要移动记录三次，因此，最大比较次数和移动次数分别为：,快速排序的基本过程,1 快速排序法是一种所需比较次数较少，目前在排序中速度较快的方法。2 其思想是取待排序的结点序列中某个结点的值作为控制值，采用某种方法把这个结点放到适当的位置，使得这个位置的左边的所有结点的值都小于等于这个控制值，而这个位置的右边的所有结点的值都大于等于这个控制值。,49,38,65,97,76,13,27,49,38,65,97,76,13,27,49,27,38,65,97,76,13,49,27,38,97,76,13,65,49,27,38,13,97,76,65,49,27,38,13,76,97,65,49,27,38,13,49,76,97,65,49,49,temp,快速排序一趟过程示例,快速排序的时间复杂度,考虑关键字的比较次数和对象移动次数1、最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准的左边（或右边）为空，划分前后无序区的元素个数减少一个，因此，排序必须做n-1趟，每一趟中需做n-i次比较，所以最大比较次数为,2、最好情况是每次所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左右两个无序子区的长度大致相等。3、快速排序的记录移动次数不会大于比较次数，所以，快速排序的最坏时间复杂度为O(n2)；最好时间复杂度为O(nlog2n)。4、快速排序的平均时间复杂度也是O(nlog2n)。,二 插入排序,基本原理，每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象适当位置上，直到对象全部插入为止。,直接（简单）插入排序(Insert Sort)希尔排序(Shell Sort),直接（简单）插入排序(Insert Sort),基本思想：当插入第i个对象时，前面V0,V1,Vi-1已经排好序，此时，用vi的关键字与Vi-1,Vi-2,的关键字顺序进行比较，找到插入位置即将Vi插入，原来位置上对象向后顺移。,直接插入排序举例,i(0)(1)(2)(3)(4)(5)temp 21 25 49 25*16 08 251 21 25 49 25*16 08 492 21 25 49 25*16 08 25*3 21 25 25*49 16 08 164 16 21 25 25*49 08 08 5 08 16 21 25 25*49,直接插入排序的时间复杂度为O(n2),希尔排序的基本过程,设待排序的对象序列有n个对象，首先取一个整数gapn作为间隔（一般取n/2），将全部对象分为gap个子序列，所有距离为gap的对象放在同一个序列中，在每一个子序列中分别施行直接插入排序，然后缩小间隔gap，如取gap=gap/2，重复上述的子序列划分和排序工作，直到最后取gap为1为止。,希尔排序示例,i(0)(1)(2)(3)(4)(5)gap 21 25 49 25*16 08 1 21-25*3 25-16 49-08 21 16 08 25*25 492 21-08-25 2 16-25*-49 08 16 21 25*25 493 08 16 21 25*25 49 1 08 16 21 25*25 49,Shell的方案是 gap=n/2,gap=gap/2，直到gap=1.,三 选择排序,基本原理:将待排序的结点分为已排序(初始为空)和为未排序两组，依次将未排序的结点中值最小的结点插入已排序的组中。,直接（简单）选择排序堆排序（自己看书了解）,简单选择排序基本过程,在一组对象Vi到Vn-1中选择具有最小关键字的对象若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对调。删除具有最小关键字的对象，在剩下的对象中重复第(1)、(2)步，直到剩余对象只有一个为止。,直接插入排序的时间复杂度为O(n2),简单选择排序示例,49,38,65,97,76,13,27,49,13,38,65,97,76,49,27,49,13,27,65,97,76,49,38,49,13,27,38,97,76,49,65,49,13,27,38,49,76,97,65,49,13,27,38,49,49,97,65,76,13,27,38,49,49,65,97,76,13,27,38,49,49,65,76,97,3.3 二叉排序树及其查找,3.3.1 二叉排序树及其构造3.3.2 二叉排序树查找,3.3.1 二叉排序树及其构造二叉排序树是指满足下列条件的二叉树：(1)左子树上的所有结点值均小于根结点值；(2)右子树上的所有结点值均不小于根结点值；(3)左、右子树也满足上述两个条件。,二叉排序树：,二叉排序树的构造过程：,依次读入给定序列中的每一个元素：(1)若当前的二叉排序树为空，则读入的元素为根结点；(2)若读入的元素值小于根结点值，则将元素插入到左子树中；(3)若读入的元素值不小于根结点值，则将元素插入到右子树中。无论是插入到左子树还是右子树，同样按照上述方法处理。,给定元素序列（80，82，85，75，82，68，71，77，88）构造二叉排序树,插入元素68,插入元素71,插入元素77,插入元素88,3.4.2 二叉排序树查找 从二叉排序树的根结点开始与被查值进行比较：(1)若被查值等于根结点值，查找成功，查找过程结束。(2)若被查值小于根结点值，则到左子树中去查找。(3)若被查值大于根结点值，则到右子树中去查找。在左、右子树中查找时也采用上述方法。查找过程直到查找成功或所考虑的子树已空为止。,二叉排序树查找输入：二叉排序树头指针BT以及存储空间；被查元素x。输出：被查元素x在二叉排序树空间中的存储结点序号p,struct btnode/*定义结点类型*/int d；/*数据域*/struct btnode*lchild；/*左指针域*/struct btnode*rchild；/*右指针域*/*bt；,/*函数返回被查值x所在结点的存储地址*/struct btnode bstserch(int x)struct btnode*p；pbt；while(p!NULL)&(pd!x)if(xpd)pplchild；/*沿左子树查找*/else pprchild；/*沿右子树查找*/return(p)；,作业：,习题3.1，3.2,对于序列（81，52，57，22，95，04，83，96），分别写出冒泡排序，简单插入排序，简单选择排序的排序过程。,实验：,对于序列（15，25，7，9，11，12）先用冒泡排序对其进行排成升序序列，再查找元素7所在数组的位置。,
