查找与排序软件基础知识.ppt
第三章 查找与排序1 基本的查找技术2 基本的排序技术3 二叉排序树及其查找3.1基本的查找技术n顺序查找n有序表的对分查找顺序查找(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 基本排序技术n交换排序（冒泡排序与快速排序）n插入排序（简单插入排序与希尔排序）n选择排序（简单选择排序与堆排序）排序的一些基本概念简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来（递增或递减）。数据表(Data List)待排序的数据对象的有限集合。关键字(Key)作为排序依据的数据对象中的属性域。主关键字 不同的数据对象若关键字互不相同，则这种关键字称为主关键字。排序的确切定义 使一组任意排列的对象变成一组按关键字线性有序的对象。排序的时间开销 它是衡量算法好坏的最重要的标志。通常用算法执行中的数据比较次数和数据移动次数来衡量。一 交换排序基本原理基本原理基本原理基本原理：两两比较待排序的对象的关键字，如：两两比较待排序的对象的关键字，如：两两比较待排序的对象的关键字，如：两两比较待排序的对象的关键字，如果发生逆序，则交换之，直到全部对象都排好序果发生逆序，则交换之，直到全部对象都排好序果发生逆序，则交换之，直到全部对象都排好序果发生逆序，则交换之，直到全部对象都排好序为止为止为止为止。两种常见的交换排序两种常见的交换排序两种常见的交换排序两种常见的交换排序冒泡排序冒泡排序冒泡排序冒泡排序(Bubble Sort)(Bubble Sort)快速排序快速排序快速排序快速排序(Quick Sort)(Quick Sort)冒泡排序的基本过程冒泡排序的基本过程1.1.假设待排序的假设待排序的假设待排序的假设待排序的n n个对象的序列为个对象的序列为个对象的序列为个对象的序列为V0,V1,.,Vn-1V0,V1,.,Vn-1，起始时排序范围是从，起始时排序范围是从，起始时排序范围是从，起始时排序范围是从V0V0到到到到Vn-1Vn-12.2.在当前的排序范围之内，自右至左对相邻的在当前的排序范围之内，自右至左对相邻的在当前的排序范围之内，自右至左对相邻的在当前的排序范围之内，自右至左对相邻的两个结点依次进行比较，让值较大的结点往下两个结点依次进行比较，让值较大的结点往下两个结点依次进行比较，让值较大的结点往下两个结点依次进行比较，让值较大的结点往下移移移移(下沉下沉下沉下沉)，让值较小的结点往上移，让值较小的结点往上移，让值较小的结点往上移，让值较小的结点往上移(上冒上冒上冒上冒)。每。每。每。每趟起泡都能保证值最小的结点上移至最左边，趟起泡都能保证值最小的结点上移至最左边，趟起泡都能保证值最小的结点上移至最左边，趟起泡都能保证值最小的结点上移至最左边，下一遍的排序范围为从下一结点到下一遍的排序范围为从下一结点到下一遍的排序范围为从下一结点到下一遍的排序范围为从下一结点到Vn-1Vn-1。3.3.在整个排序过程中，最多执行在整个排序过程中，最多执行在整个排序过程中，最多执行在整个排序过程中，最多执行(n-1)(n-1)遍。但执遍。但执遍。但执遍。但执行的遍数可能少于行的遍数可能少于行的遍数可能少于行的遍数可能少于(n-1)(n-1)，这是因为在执行某一，这是因为在执行某一，这是因为在执行某一，这是因为在执行某一遍的各次比较没有出现结点交换时，就不用进遍的各次比较没有出现结点交换时，就不用进遍的各次比较没有出现结点交换时，就不用进遍的各次比较没有出现结点交换时，就不用进行下一遍的比较行下一遍的比较行下一遍的比较行下一遍的比较冒泡排序示例i (0)(1)(2)(3)(4)(5)i (0)(1)(2)(3)(4)(5)21 25 49 25*16 08 21 25 49 25*16 08 1 1 0808 21 25 49 25*16 21 25 49 25*16 2 2 08 1608 16 21 25 49 25*21 25 49 25*3 3 08 16 21 08 16 21 25 25*49 25 25*49 4 4 08 16 21 25 08 16 21 25 25*25*49 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 1、在最好情况下，初始状态是递增有序的，一趟扫描就可完成排、在最好情况下，初始状态是递增有序的，一趟扫描就可完成排、在最好情况下，初始状态是递增有序的，一趟扫描就可完成排、在最好情况下，初始状态是递增有序的，一趟扫描就可完成排序，关键字的比较次数为序，关键字的比较次数为序，关键字的比较次数为序，关键字的比较次数为n-1n-1，没有记录移动。，没有记录移动。，没有记录移动。，没有记录移动。2 2、若初始状态是反序的，则需要进行、若初始状态是反序的，则需要进行、若初始状态是反序的，则需要进行、若初始状态是反序的，则需要进行n-1n-1趟扫描，每趟扫描要进趟扫描，每趟扫描要进趟扫描，每趟扫描要进趟扫描，每趟扫描要进行行行行n-in-i次关键字的比较，且每次需要移动记录三次，因此，最大比次关键字的比较，且每次需要移动记录三次，因此，最大比次关键字的比较，且每次需要移动记录三次，因此，最大比次关键字的比较，且每次需要移动记录三次，因此，最大比较次数和移动次数分别为：较次数和移动次数分别为：较次数和移动次数分别为：较次数和移动次数分别为：快速排序的基本过程1 1 快速排序法是一种所需比较次数较少，目前在排快速排序法是一种所需比较次数较少，目前在排快速排序法是一种所需比较次数较少，目前在排快速排序法是一种所需比较次数较少，目前在排序中速度较快的方法。序中速度较快的方法。序中速度较快的方法。序中速度较快的方法。2 2 其思想是取待排序的结点序列中某个结点的值作其思想是取待排序的结点序列中某个结点的值作其思想是取待排序的结点序列中某个结点的值作其思想是取待排序的结点序列中某个结点的值作为控制值，采用某种方法把这个结点放到适当的位为控制值，采用某种方法把这个结点放到适当的位为控制值，采用某种方法把这个结点放到适当的位为控制值，采用某种方法把这个结点放到适当的位置，使得这个位置的左边的所有结点的值都小于等置，使得这个位置的左边的所有结点的值都小于等置，使得这个位置的左边的所有结点的值都小于等置，使得这个位置的左边的所有结点的值都小于等于这个控制值，而这个位置的右边的所有结点的值于这个控制值，而这个位置的右边的所有结点的值于这个控制值，而这个位置的右边的所有结点的值于这个控制值，而这个位置的右边的所有结点的值都大于等于这个控制值。都大于等于这个控制值。都大于等于这个控制值。都大于等于这个控制值。4938659776132749 38659776132749273865977613 492738 97761365492738139776 6549273813 76976549273813 49 76 97 654949temp快速排序一趟过程示例快速排序的时间复杂度快速排序的时间复杂度考虑关键字的比较次数和对象移动次数考虑关键字的比较次数和对象移动次数考虑关键字的比较次数和对象移动次数考虑关键字的比较次数和对象移动次数1 1、最坏情况是每次划分选取的基准都是当前无序区中关键字最、最坏情况是每次划分选取的基准都是当前无序区中关键字最、最坏情况是每次划分选取的基准都是当前无序区中关键字最、最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准的左边（或右边）为空，小（或最大）的记录，划分的结果是基准的左边（或右边）为空，小（或最大）的记录，划分的结果是基准的左边（或右边）为空，小（或最大）的记录，划分的结果是基准的左边（或右边）为空，划分前后无序区的元素个数减少一个，因此，排序必须做划分前后无序区的元素个数减少一个，因此，排序必须做划分前后无序区的元素个数减少一个，因此，排序必须做划分前后无序区的元素个数减少一个，因此，排序必须做n-1n-1趟，趟，趟，趟，每一趟中需做每一趟中需做每一趟中需做每一趟中需做n-in-i次比较，所以最大比较次数为次比较，所以最大比较次数为次比较，所以最大比较次数为次比较，所以最大比较次数为2、最好情况是每次所取的基准都是当前无序区的、最好情况是每次所取的基准都是当前无序区的“中值中值”记录，划记录，划分的结果是基准的左右两个无序子区的长度大致相等。分的结果是基准的左右两个无序子区的长度大致相等。3、快速排序的记录移动次数不会大于比较次数，所以，快速排序的、快速排序的记录移动次数不会大于比较次数，所以，快速排序的最坏时间复杂度为最坏时间复杂度为O(n2)；最好时间复杂度为；最好时间复杂度为O(nlog2n)。4、快速排序的平均时间复杂度也是、快速排序的平均时间复杂度也是O(nlog2n)。二 插入排序基本原理，每步将一个待排序的对象，按其关基本原理，每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象键字大小，插入到前面已经排好序的一组对象适当位置上，直到对象全部插入为止。适当位置上，直到对象全部插入为止。直接（简单）插入排序直接（简单）插入排序直接（简单）插入排序直接（简单）插入排序(Insert Sort)(Insert Sort)希尔排序希尔排序希尔排序希尔排序(Shell Sort)(Shell Sort)直接（简单）插入排序直接（简单）插入排序(Insert Sort)基本思想：当插入第基本思想：当插入第基本思想：当插入第基本思想：当插入第i i个对象时，前面个对象时，前面个对象时，前面个对象时，前面V0,V1,Vi-1V0,V1,Vi-1已经排好序，此时，用已经排好序，此时，用已经排好序，此时，用已经排好序，此时，用vivi的关的关的关的关键字与键字与键字与键字与Vi-1,Vi-2,Vi-1,Vi-2,的关键字顺序进行比较，找的关键字顺序进行比较，找的关键字顺序进行比较，找的关键字顺序进行比较，找到插入位置即将到插入位置即将到插入位置即将到插入位置即将ViVi插入，原来位置上对象向后顺移。插入，原来位置上对象向后顺移。插入，原来位置上对象向后顺移。插入，原来位置上对象向后顺移。直接插入排序举例直接插入排序举例直接插入排序举例直接插入排序举例i (0)(1)(2)(3)(4)(5)tempi (0)(1)(2)(3)(4)(5)temp 2121 25 49 25*16 08 25 25 49 25*16 08 251 1 21 2521 25 49 25*16 08 49 49 25*16 08 492 2 21 25 4921 25 49 25*16 08 25*25*16 08 25*3 3 21 25 25*4921 25 25*49 16 08 16 16 08 164 4 16 21 25 25*4916 21 25 25*49 08 08 08 08 5 5 08 16 21 25 25*4908 16 21 25 25*49 直接插入排序的时间复杂度为O(n2)希尔排序的基本过程希尔排序的基本过程设待排序的对象序列有设待排序的对象序列有设待排序的对象序列有设待排序的对象序列有n n个对象，首先取一个整数个对象，首先取一个整数个对象，首先取一个整数个对象，首先取一个整数gapngapd!x)if(xpd)pplchild；/*沿左子树查找*/else pprchild；/*沿右子树查找*/return(p)；作业：习题3.1，3.2对于序列（81，52，57，22，95，04，83，96），分别写出冒泡排序，简单插入排序，简单选择排序的排序过程。实验：n对于序列（15，25，7，9，11，12）先用冒泡排序对其进行排成升序序列，再查找元素7所在数组的位置。
