第1章-10+排序.ppt

1、本节基本内容与要求,基本内容 顺序查找、二分查找、二叉树查找以及散列表上查找 及算法思想 排序的基本概念以及选择、插入、交换和归并四类排序的基本思想和算法 要求 掌握线性表、树和散列表(或称哈希表)的查找方法及算法实现以及各种查找方法的应用 熟练掌握选择、插入、交换和归并四类排序的基本思想和算法,1.4 内部排序,一、基本概念 二、选择排序 三、插入排序 四、交换排序 五、归并排序,一、基本概念,1. 排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。,例如：下列是一组记录对应的关键字序列,(52, 49, 80, 36, 14, 58, 61, 23, 97,

2、75),调整为,(14, 23, 36, 49, 52, 58, 61 ,75, 80, 97),2. 排序的定义,假设含n个记录的序列为 R1, R2, ， Rn 其相应的关键字序列为 K1, K2, ，Kn 这些关键字相互之间可以进行比较，即在 它们之间存在着这样一个关系 ： Kp1Kp2Kpn 按此固有关系将上式记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作排序。,3、排序的基本操作,排序的概念：就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。 排序过程的组成步骤：首先比较两个关键字的大小； 然后将记录从一个位置移动到另一个位置。 对记录的关键字大小进行比较

3、 将记录从一个位置移动到另一个位置 当待排序记录的关键字均不相同时，则排序结果是唯一的，否则排序的结果不一定唯一。,4、排序的稳定性,若有： R1 ,., Ri,.,Rj,. 且关键字： Ki=Kj ij 排序后： Ri,Rj,. 则称该排序结果具有稳定性。,在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的； 若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。,内部排序：是指在排序的整个过程中，数据全部存放在计算机的内存储器里，并且在内存储器里调整数据的位置； 当文件很大以致内存不足以存放全部数据

4、时，在排序过程中需要对外存进行存取访问，称这种借助于外存储器进行排序的方法为外部排序。 注意： 内排序适用于记录个数不很多的小文件 外排序则适用于记录个数太多，不能一次将其全部记录放入内存的大文件。,5、排序的分类,二、选择排序,直接选择排序 又称为简单选择排序，是一种简单直观的排序方法。 从待排序的所有记录中，选取关键字最小的记录，并将它与原始序列中的第一个记录交换，然后从去掉了关键字最小记录的剩余记录中选择关键字最小的记录将它与原始记录序列的第二个记录交换位置，以此类推，直到序列中全部记录排序完毕。,算法： void selectsort(elemtype x,int n) /对记录序列x

5、0 xn-1进行直接选择排序 int i,j,small; elemtype swap; for(i=0;in-1;i+) small=i; for(j=i+1;jn;j+) if(xj.keyxsmall.key) small=j; if(small!=i) swap=xi; Xi=xsmall; Xsmall=swap; ,三、插入排序,每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。 把新元素（未排序的元素的关键字）逐个插入正在增长的顺序表中。 寻找插入位置的方法： 线性插入排序 对半插入排序 希尔排序,有序序列L.r1.i-1,

6、L.ri,无序序列 L.ri.n,有序序列L.r1.i,无序序列 L.ri+1.n,1、线性插入排序,基本思想：每步将一个待排序的元素按其大小插入到前面已排序的数据中的适当位置。重复该工作，直至有序区包含所有元素。,方法：,具体方法：先将第一个数据看成是一个有序的子序列，然后从第2个数据起逐个插入到这个有序的子序列中去，相应的元素要移动。,3将L.ri 插入到L.rj+1的位置上。,2将L.rj+1.i-1中的所有记录均后移 一个位置；,1在L.r1.i-1中查找L.ri的插入位置， L.r1.j L.ri L.rj+1.i-1；,该算法适合于n 较小的情况，时间复杂度为O(n2).,待排元素

7、序列：53 27 36 15 69 42 第一次排序： 27 53 36 15 69 42 第二次排序： 27 36 53 15 69 42 第三次排序： 15 27 36 53 69 42 第四次排序： 15 27 36 53 69 42 第五次排序： 15 27 36 42 53 69 线性插入排序示例,对于有n个数据元素的待排序列，插入操作要进行n-1次,例：,void insertSort(RedType L ,int n) int i ,j; for(i=2; i=n; i+) L0=Li; / 作为监视哨 for( j=i-1; L0.keyLj.key; j ) Lj+1=Lj;

8、 /记录后移 Lj+1=L0; / 插入 ,插入算法,方法:Ki与Ki-1,K i-2,K1依次比较,直到找到应插入的位置。,哨兵(监视哨),哨兵(监视哨)有两个作用 作为临时变量存放Ri(当前要进行比较的关键字)的副本； 在查找循环中用来监视下标变量j是否越界。,R0 R1 R2 R3 R4 R5 6 2061573 15 6201573 7 6152073 36715203 3671520,直接插入排序的程序： #include stdio.h #define n 5 int arn; int c,t; void d_insort(a) int an; int i,j; for (i=2;

9、i0) ,main() int i; printf(请输入数据: ); for (i=1;i=n;i+) scanf(%d, 运行结果： 请输入数据: 50 60 20 40 80 排序后的序列: 20 |40 |50 |60 |80 |,性能分析,最好情况（原始记录按关键字有序排列）：O（n）,“比较”的次数：,最坏情况（原始记录按关键字逆序排列）：O（n2）,“比较”的次数：,0,“移动”的次数：,“移动”的次数：,结论：适用原始数据基本有序或数据量不大的情况。,希尔排序（Shells method）又称为“缩小增量排序” ，本质上讲是插入排序，它是对线性插入排序的改进。 其基本思想是：

10、先取一个小于n的整数d1并作为第一个增量，将文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序； 然后取第二个增量d2d1，重复上述的分组和排序，直至所取的增量dt=1 (dtdt1d2d1)为止，此时，所有的记录放在同一组中进行直接插入排序。,2 希尔插入排序算法思想,如何选择增量序列才能产生最好的排序效果，这个问题至今没有得到解决。 希尔本人最初提出取 d1=n/2， di+1=di/2， dt=1，t=log2n。,希尔插入排序步骤,（1）首先选取一个整数d1n（n为待排序数据的个数），作为两个数据之间的距离，这样把全部数据分成d1个组，凡是距离

11、为d1的数据放在一个组里，在各组内进行内部排序，直到各组排好序为止。 （2）从上述的结果序列出发，再选择d2d1，重复上面的分组与排序工作。 （3）依次取di+1di，直到dm=1（设一共需要m次分组），即所有数据放在一组中排序为止。此时，全部数据便按次序排好了。,设待排序共有10个记录，其关键字分别为47, 33, 61, 82, 71, 11, 25, 47, 57, 02，增量序列取值依次为5, 3, 1。,希尔插入排序过程,希尔排序实质上还是一种插入排序，其主要特点是： 每一趟以不同的增量进行排序。在每趟的插入排序中，记录的关键字是和同一组中的前一个关键字进行比较，所以关键字较小的记录

12、在排序过程中是作跳跃式的移动。 另外，由于开始时增量的取值较大，每组中记录较少，故排序比较快，随着增量值的逐步变小，每组中的记录逐渐变多，但由于此时记录已基本有序了，因次在进行最后一趟增量为1的插入排序时，只需作少量的比较和移动便可完成排序，从而提高了排序速度。,希尔插入排序特点,希尔排序比直接插入排序的平均性能要好： 在最好情况（原始记录按关键字有序排列）下，移动次数为0，比较次数界于n n2 之间。 在最坏情况（原始记录按关键字逆序排列）下，移动次数和比较次数接近n2。 在平均情况下，移动次数和比较次数在O（n1.3）左右，好于直接插入排序。,希尔插入排序性能效率,例1.19 希尔排序的程

13、序 #include stdio.h #define max 10 int datamax+1; int indexmax+1; int i;,void shell_sort(a) int amax+1; int i,j,n,m,skip; int alldone; for (i=1;i1) skip=skip/2; do alldone=1; for (j=1;j=max-skip;j+) i=j+skip; n=indexi; m=indexj; if (anam) indexi=m; indexj=n; alldone=0; while (alldone=0); ,main() prin

14、tf(请输入数据: ); for (i=1;i=max;i+) scanf(%d, ,运行结果： 请输入数据: 19 41 11 17 47 43 13 37 31 23 19 41 11 17 47 43 13 37 31 23 11 13 17 19 23 31 37 41 43 47 希尔排序的分析较为复杂，因为它的时间是所取“增量”序列的函数，这涉及到一些数学上尚未解决的难题。增量序列可以有各种取法，但需注意：应使增量序列中的值没有除1以外的公因子，并且最后一个增量值必须等于1。,2. 希尔排序,四、交换排序,两两比较待排序记录的关键字，发现两个记录次序相反时即进行交换，直到没有反序的

15、记录为止。 冒泡排序 快速排序,首先对无序的记录序列进行“一次划分”，通过一趟排序将待排序列分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分排序，以达到整个序列有序。,无 序 的 记 录 序 列,无序记录子序列(1),无序子序列(2),枢轴,一次划分,分别进行快速排序,快速排序基本思想,快速排序 方法,目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录移至该记录之前，反之，移至该记录之后。 关键字通常取第一个记录的值为基准值。 方法：附设两个指针i和j ，初值分别指向第一个记录和最后一个记录，设关键字为 key ，首先从 j所指位置起向前搜索，找到第一个小

16、于基准值的记录与基准记录交换，然后从i 所指位置起向后搜索，找到第一个大于基准值的记录与基准记录交换，重复这两步直至i=j为止。,快速排序一趟算法,初始值 46 55 13 42 94 5 17 70,17 55 13 42 94 5 17 70,17 55 13 42 94 5 55 70,基准X=46,17 5 13 42 94 5 55 70,17 5 13 42 94 94 55 70,17 5 13 42 94 94 55 70,46,快速排序例,初始值 46 55 13 42 94 5 17 70,第一趟 13 5 17 42 46 94 55 70,第二趟 5 13 17 42

17、46 70 55 94,第三趟 5 13 17 42 46 55 70 94,第四趟 5 13 17 42 46 55 70 94,快速排序步骤,(1)令指针L1 ，Rn ，即分别指向A1和An； (2)自尾端开始进行比较：将AR与AL比较，若ALAR，则数据就不交换，此时固定L（即L指针不动），调整尾指针，使RR-1。继续比较，直至ALAR时为止，将AR与AL交换位置，并修改左指针，使LL+1； (3)将AL与AR比较，若ALAR，则调整左指针，使LL+1，R指针不动。继续比较，直至ALAR时为止，将AL与AR交换位置，并修改右指针R，使RR-1； (4)重复(2)(3)步骤，直到从两边开始

18、的扫描在中间相遇，即L、R指针重合于中间某一个元素，此时该元素即在排序的序列中找到了自己合适的位置，并且此元素将原序列分成了前后两个子集。虽然此时这两个子集还是无序的，但前一个子集的所有元素均小于后一个子集的所有元素。这称为一趟。,low,high,设 L.rlow=52 为枢轴,将 L.rhigh和枢轴的关键字进行比较，要求L.rhigh枢轴的关键字,将 L.rlow和枢轴的关键字进行比较，要求L.rlow枢轴的关键字,high,23,low,80,high,14,low,52,52,high,high,high,low,快速排序一次划分的过程,经过“一次划分” ，将关键字序列 52, 49

19、, 80, 36, 14, 58, 61, 97, 23, 75 调整为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75,在调整过程中，设立了两个指针： low 和high，之后逐渐减小 high或增加 low，并保证： L.rhigh52且L.rlow52, 否则进行记录的“交换”。,快速排序一次划分的结果,快速排序算法,void quicksort(int r ,int left,int right) int i=left,j=right; int x=ri; while (i=x) /递归调用右子区间 ,快速排序的时间主要耗费在划分操作上，对长度为k的区

20、间进行划分，共需k-1次关键字的比较。,最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1in-1)，故总的比较次数达到最大值： n(n-1)/2=O(n2),快速排序时间分析,在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数： O(nlogn),因为快速

21、排序的记录移动次数不大于比较的次数，所以快速排序： 最坏时间复杂度应为O (n2) 最好时间复杂度为O(nlogn) 平均时间复杂度为O(nlogn),快速排序时间分析,快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O(logn)，故递归后需栈空间为O(logn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。,因为快速排序的划分次数在lognn之间，所以快速排序的： 最坏空间复杂度应为O (n) 最好空间复杂度为O(logn) 平均空间复杂度为O(logn),快速排序空间分析,快速排序的程序： #include stdio.h #define n

22、 10 int arn+1; int i,l1; int quick1(a,l,r) int an+1; int l,r; /* 指针 */ int l1; int r1,w; l1=l; r1=r; w=al1; do while (ar1=w) ,void q_sort(a,l,r) int an+1; int l,r; int l1; if (lr) l1=quick1(a,l,r); q_sort(a,l,l1-1); q_sort(a,l1+1,r); ,main() printf(请输入数据: n); for (i=1;i=n;i+) scanf(%d, ,运行结果： 请输入数据:

23、 42 23 74 11 65 58 94 36 99 87 排序后的序列: 11 23 36 42 58 65 74 87 94 99,归并排序又称为表排序，其含义是将两个有序序列合并成为一个有序序列。1、基本思想 设待排序序列有n个记录，开始将其看作是n个长度为1 的有序子文件，然后进行归并，将相邻的有序子文件两两合并，得到n/2个长度为2或1的有序子文件(如果n为奇数，则最后一个有序子文件的长度为1)，再两两归并得到n/4个有序子文件，以此类推，直至得到长为n的有序文件。该有序序列就是原始序列经归并排序后的有序序列。在排序过程中，子序列总是两两归并，所以归并排序又被称为二路归并排序。,五

24、、归并排序,例如对序列16，31，9，15，87，76，13，24，43进行二路归并排序过程为：,2、二路归并的算法 在编写程序实现时，实际上是把两个长度为k的有序序列连接合并成一个长度为2k的有序序列。可利用三个指针分别指向三个序列的第一个元素，将两个序列的第一个元素进行比较，取出关键字较小者作为结果序列的第一个元素，将较小者所在序列及结果序列的指针后移，继续比较和加入。最后当两个序列之一的所有元素都取完时，再将另一序列的剩余元素顺序复制到结果序列中，完成归并。,void merge(r,r1,low,mid,high) /rlow到rmid与rmid+1到rhigh是两个有序子文件 /本算

25、法将其归并成一个有序子文件从r1low到r1high rectype r,r1; int low,mid,high; int i=low; j=mid+1; k=low; while (i=mid) /复制第二个文件剩余记录 ,void mergepass(r,r1,length) /对r进行一趟归并，结果放在r1中 rectype r,r1; int length; / length是本趟归并的有序子文件的长度 int i=0,j; /指向第一对子文件起始点 while (i+2*length=n) merge(r,r1,i,i+length-1,i+2*length-1) i=i+2*le

26、ngth /指向下一对子文件起始点 if (i+leng-1n-1) /剩下两个子文件，其中一个长度小于length merge(r,r1,i,i+length-1,n-1); else /子文件个数为奇数，将最后一个子文件复制到r1中 for (j=i;jn;j+) r1j=rj; ,void mergesort( r ) rectype r; int length=1; while (lengthn) mergepass(r,r1,length) ; / 一趟归并，结果在r1中 length=2*length; /区间扩大一倍 mergepass(r1,r,length) ; / 再次归并

27、，结果在r中 lenth=2*length; ,3、二路归并的算法分析 第i趟排序后，有序子文件长度为2i，具有那个记录的文件排序，必须做log2n趟归并，每趟所花时间为O(0)，所以二路归并排序的时间复杂度为O(nlog2n) ，所需的空间为O(0)。,2. 堆排序 堆就是一个关键字序列：并且这n个关键字的序列K1,K2.Kn要满足以下性质(堆性质)，就是: KiK2i且KiK2i+1 或者 KiK2i且KiK2i+1,当把这个序列存入一个向量并把它看作是一棵完全二叉树的存储结构时，堆就是这样一棵二叉树：任一非叶结点的关键字均不小于(或不大于)其左右孩子结点的关键字。,1 2 3 4 5 6

28、 7 8,最大值,a) 堆顶元素取最大值 大根堆,b) 堆顶元素取最小值 小根堆,堆排序基本思想,因为堆顶是最大的数，所以当把一个关键字序列排成一个大根堆时，就很容易地找到最大的数，它就在序列的第一个位置上 然后把这个最大的数与最后一个记录交换，这时，最后一个记录就是关键字最大的记录了。 对于剩下的关键字序列，我们仍然把它排成一个大根堆，然后再把第一个记录(当前堆中的堆顶)与当前堆的最后一个记录交换。这时，在整个序列后面就有了两个有序的关键字(从小到大)。 重复这样的过程，就可以把有序区不断扩大直到全部关键字都进入有序区。直到排序完成。,堆的构造,无序序列r1：n构成的完全二叉树。 从它最后一

29、个非叶子结点（第n/2个元素）开始直到根结点为止，逐步进行调整即可将此完全二叉树构成堆。 调整：与其左右子树根结点值比较，取其中大的进行交换。,堆的构造例,46 55 13 42 94 05 17 70,70,17,05,94,42,13,55,46,1 2 3 4 5 6 7 8,70,17,05,94,42,13,55,46,1 2 3 4 5 6 7 8,对调,对调,42,17,05,94,70,13,55,46,1 2 3 4 5 6 7 8,对调,对调,13,13,堆的构造例,46 55 13 42 94 05 17 70,42,13,05,94,70,17,55,46,1 2 3 4 5 6 7 8,对调,55,55,对调,42,13,05,55,70,17,94,46,1 2 3 4 5 6 7 8,对调,46,46,对调,堆的构造例,46 55 13 42 94 05 17 70,42,13,05,55,70,17,46,94,1 2 3 4 5 6