查找与排序软件基础知识.ppt

《查找与排序软件基础知识.ppt》由会员分享，可在线阅读，更多相关《查找与排序软件基础知识.ppt（38页珍藏版）》请在装配图网上搜索。

1、第三章 查找与排序,1 基本的查找技术 2 基本的排序技术 3 二叉排序树及其查找,3.1基本的查找技术,顺序查找 有序表的对分查找,3.1.1顺序查找,(1)如果线性表为无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。 (2)即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。,线性表在顺序存储结构下的顺序查找 输入：线性表长度n以及线性表的存储空间V；被查找的元素x。 输出：被查找元素x在线性表中的序号k。如果在线性表中不存在元素x，则输出k1。,int serch (int v，int n，int x) int k； k0； while

2、(kn) 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 其思

3、想是取待排序的结点序列中某个结点的值作为控制值，采用某种方法把这个结点放到适当的位置，使得这个位置的左边的所有结点的值都小于等于这个控制值，而这个位置的右边的所有结点的值都大于等于这个控制值。,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、

4、最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准的左边（或右边）为空，划分前后无序区的元素个数减少一个，因此，排序必须做n-1趟，每一趟中需做n-i次比较，所以最大比较次数为,2、最好情况是每次所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左右两个无序子区的长度大致相等。 3、快速排序的记录移动次数不会大于比较次数，所以，快速排序的最坏时间复杂度为O(n2)；最好时间复杂度为O(nlog2n)。 4、快速排序的平均时间复杂度也是O(nlog2n)。,二 插入排序,基本原理，每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象

5、适当位置上，直到对象全部插入为止。,直接（简单）插入排序(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 25 1 21 25 49 25* 16 08 49 2 21 25 49 25* 16 08 25* 3 21 25 25* 49

6、 16 08 16 4 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

7、25 - - 16 49 - - 08 21 16 08 25* 25 49 2 21 - 08 - 25 2 16 - 25* - 49 08 16 21 25* 25 49 3 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中选择具有最小关键字的对象 若它不是这

8、组对象中的第一个对象，则将它与这组对象中的第一个对象对调。 删除具有最小关键字的对象，在剩下的对象中重复第(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

9、二叉排序树及其查找,3.3.1 二叉排序树及其构造 3.3.2 二叉排序树查找,3.3.1 二叉排序树及其构造 二叉排序树是指满足下列条件的二叉树： (1)左子树上的所有结点值均小于根结点值； (2)右子树上的所有结点值均不小于根结点值； (3)左、右子树也满足上述两个条件。,二叉排序树：,二叉排序树的构造过程：,依次读入给定序列中的每一个元素： (1)若当前的二叉排序树为空，则读入的元素为根结点； (2)若读入的元素值小于根结点值，则将元素插入到左子树中； (3)若读入的元素值不小于根结点值，则将元素插入到右子树中。 无论是插入到左子树还是右子树，同样按照上述方法处理。,给定元素序列（80，

10、82，85，75，82，68，71，77，88）构造二叉排序树,插入元素68,插入元素71,插入元素77,插入元素88,3.4.2 二叉排序树查找 从二叉排序树的根结点开始与被查值进行比较： (1)若被查值等于根结点值，查找成功，查找过程结束。 (2)若被查值小于根结点值，则到左子树中去查找。 (3)若被查值大于根结点值，则到右子树中去查找。 在左、右子树中查找时也采用上述方法。 查找过程直到查找成功或所考虑的子树已空为止。,二叉排序树查找 输入：二叉排序树头指针BT以及存储空间；被查元素x。 输出：被查元素x在二叉排序树空间中的存储结点序号p,struct btnode /*定义结点类型*/

11、 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所在数组的位置。,