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

《查找与排序软件基础知识.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、intx){intk；k＝0；while((k＜n)&&(v[k]≠x))k＝k＋1；if(k＝＝n)k＝－1；return(k)；}3.1.2有序表的对分查找设有序线性表的长度为n，被查元素为x。将x与线性表的中间项进行比较：若中间项的值等于x，则说明查到，查找结束；若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0(说明线性表中没有这个元素)为止。在最坏

3、情况下，对分查找只需比较log2n次，而顺序查找需比较n次。有序线性表在顺序存储结构下的对分查找输入：有序线性表长度n以及线性表的存储空间V；被查找的元素x。输出：被查找元素x在有序线性表中的序号k。如果在线性表中不存在元素x，则输出k＝－1。intbserch(intv[]，intn，intx){inti，j，k；i＝1；j＝n；while(i＜＝j){k＝(i＋j)/2；if(v[k－1]＝＝x)return(k－1)；if(v[k－1]＞x)j＝k－1；elsei＝k＋1；}return(－1)；}3.2基

4、本排序技术交换排序（冒泡排序与快速排序）插入排序（简单插入排序与希尔排序）选择排序（简单选择排序与堆排序）排序的一些基本概念简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来（递增或递减）。数据表(DataList)待排序的数据对象的有限集合。关键字(Key)作为排序依据的数据对象中的属性域。主关键字不同的数据对象若关键字互不相同，则这种关键字称为主关键字。排序的确切定义使一组任意排列的对象变成一组按关键字线性有序的对象。排序的时间开销它是衡量算法好坏的最重要的标志。通常用算法执行中的数据比较次数和数据移

5、动次数来衡量。一交换排序基本原理：两两比较待排序的对象的关键字，如果发生逆序，则交换之，直到全部对象都排好序为止。两种常见的交换排序冒泡排序(BubbleSort)快速排序(QuickSort)冒泡排序的基本过程1.假设待排序的n个对象的序列为V[0],V[1],...,V[n-1]，起始时排序范围是从V[0]到V[n-1]2.在当前的排序范围之内，自右至左对相邻的两个结点依次进行比较，让值较大的结点往下移(下沉)，让值较小的结点往上移(上冒)。每趟起泡都能保证值最小的结点上移至最左边，下一遍的排序范围为从下一结

6、点到V[n-1]。3.在整个排序过程中，最多执行(n-1)遍。但执行的遍数可能少于(n-1)，这是因为在执行某一遍的各次比较没有出现结点交换时，就不用进行下一遍的比较冒泡排序示例i(0)(1)(2)(3)(4)(5)21254925*160810821254925*162081621254925*30816212525*4940816212525*49冒泡排序算法voidbubblesort(intR[],intn){inti,j,flag;inttemp;for(i=0;i

7、r(j=n-1;j>=i;j--){if(R[j+1]

8、一种所需比较次数较少，目前在排序中速度较快的方法。2其思想是取待排序的结点序列中某个结点的值作为控制值，采用某种方法把这个结点放到适当的位置，使得这个位置的左边的所有结点的值都小于等于这个控制值，而这个位置的右边的所有结点的值都大于等于这个控制值。4938659776132749’38659776132749’27386597761349’27389776136549’2