排序.ppt.ppt

排 序,10.1 基本概念,排序是将一组任意序列的数据元素（记录），按由大到小的顺序（降序）排列或按由小到大的顺序（升序）排列。这些数据元素（记录）可以是数值型，也可以为字符型。若为数值型，则按数值大小排列；若为字符型，则按其ASCII码的顺序排列。,排序的分类,（1）根据排序过程中所涉及的存储器，可分为内部排序和外部排序。内部排序：排序的所有记录都是在计算机的内存中进行的。外部排序：必须要借助于外存才能进行的排序。（2）按排序的稳定性，可将排序分为稳定排序和不稳定排序。设两个记录Ri与Rj的关键字为Ki与Kj，若Ki=Kj；若在排序前的序列中Ri在Rj之前（即ij）,且在排序后的序 列中Ri仍在Rj之前，则称所用的排序方法是稳定的，即稳定排序；反之，若排序后Ri在Rj之后，则称所用的排序方法是不稳定的，即不稳定排序。（3）按排序所采用的策略，可将排序分为插入排序、交换排序、选择 排序、归并排序和基数排序。,排序的分类,插入排序直接插入排序、希尔排序（略）交换排序冒泡排序、快速排序选择排序直接选择排序、堆排序（略）归并排序基数排序（略）,10.2 插入排序,待排序记录的数据结构:假定待排序记录是整型数据，记录的关键字即为该整数，记录个数为n，这一组记录存放在数组R中，且排序是按关键字由小到大的顺序排序。插入排序基本思想:就是依次将无序序列中的一个待排序记录，按其关键字值的大小插入到已排好序的子序列的适当位置，使得该序列有序，直到整个记录序列有序为止。由于查找待排序记录的插入位置的方法不同，插入排序的方法也有多种，本节介绍最简单的插入排序：直接插入排序。,10.2.1 直接插入排序,假设待排序的记录序列为R1，R2，R3，Rn，将该序列分成两部分，前一部分R1，R2，Ri-1是(1in)已排好序的，后一部分Ri，Ri+1，Rn是未排好序的。这时，用未排序记录序列中的第一个记录Ri分别与记录R1，R2，Ri-1进行比较，找出相应的插入位置，然后将记录Ri插入到该位置，原位置的记录向后顺推，重复这个插入过程，直到所有未排序部分的记录都插入到有序序列中。,直接插入排序的基本思想是：,在直接插入排序过程中，每将一个记录插入到前面已排好序的记录序列中，称为一趟直接插入排序。一趟插入排序的基本思想为：将记录Ri插入到有序子序列R1.i-1中，使记录的有序序列从R1.i-1变为R1.i。显然，完成这个“插入”需分三步进行：（1）查找Ri的插入位置j+1；（2）将Rj+1.i-1中的记录后移一个位置；（3）将Ri复制到Rj+1的位置上。,已知一关键字序列（48，62，35，77，55，14，35,98），请给出采用直接插入排序的方法对这8个数按升序排序时的每一趟排序过程。,例,void insertsort(int R,int n)int i,j,;for(i=2;i=n;i+)R0=Ri;/*R0中存放待插入记录*/j=i-1;/*在有序子序列中查找它的插入位置*/while(R0Rj)Rj+1=Rj;j-;/*将所有比它大的记录后移*/Rj+1=R0;/*将待插入记录插入*/,直接插入排序的算法：,直接插入排序算法的性能,时间复杂度:直接插入排序的时间复杂度为(n2)。空间复杂度:从所需的附加空间来看，直接插入排序只需要一个记录的附加空间，所以其空间复杂度为(1)。稳定性:从排序的稳定性来看，直接插入排序是稳定的。,从键盘上输入10个整数，用直接插入排序的方法对这10个数按由大到小的顺序排序并输出。编写出相应的C语言程序。分析：需要注意是，在介绍直接插入排序算法时，排序是按由小到大的顺序排列，而本例要求是按由大到小的顺序排列。所以，在寻找插入位置时，要将上面算法的for语句中的条件R0Rj。对上面算法稍作修改，写出本例的C语言程序如下：,例 10-1,#define N 10#include void main()int i,j,RN+1;for(i=1;iRj;j-)Rj+1=Rj;Rj+1=R0;for(i=1;i=N;i+)/*输出排好序的有序序列*/printf(“%d”,Ri);,例10-1程序：,10.3 交换排序,交换排序的特点是对待排序记录序列中的记录，两两比较记录关键字值，并对逆序的两个记录进行交换，直到整个序列中没有反序的记录对为止。本节将介绍两种最常见的交换排序方法：冒泡排序和快速排序。,10.3.1 冒泡排序 冒泡排序的基本思想 在待排序的记录序列中，从第一个待排序的记录R1开始，依次比较两个相邻记录R1和R2，若R1R2，则交换记录R1 和R2，否则不交换。然后再对R2 和R3进行同样的比较，依次类推，直到序列中的最后两个记录处理完为止。这样的一个过程就叫做一趟冒泡排序。这样，在一趟比较完毕后，关键字值最大的记录就被交换到最后，然后再对前面的n-1个记录执行上述过程，如此重复n-1次。,已知一关键字序列（35，14，8，16，39，2，27），请给出采用冒泡排序的方法对这7个数按升序排序时的第一趟排序过程。,例,void bubblesort(int R,int n)int i,j;for(i=1;iRj+1)R0=Rj;/*交换两个记录*/Rj=Rj+1;Rj+1=R0;,冒泡排序的算法：,从算法可知，对n个记录进行排序需要进行n-1趟排序。但实际上，除非是逆序的情况，一般情况下不需要进行n-1趟。,void bubblesort(int R,int n)int i,j,flag;/*flag记录一趟排序过程中是否有记录交换*/flag=1;/*flag=1表示有记录交换，=0表示无交换*/for(i=1;iRj+1)flag=1;/*发生交换时，设flag=1*/R0=Rj;Rj=Rj+1;Rj+1=R0;,冒泡排序改进后的算法：,时间复杂度：冒泡排序算法的时间复杂度为(n2)。空间复杂度：从所需的附加空间来看,冒泡排序仅需一个记录的附加空间，所以其空间复杂度为(1)。稳定性：从排序的稳定性来看，冒泡排序是稳定的。,冒泡排序算法的性能：,用冒泡法将从键盘输入的10个整数按由小到大的顺序排序。,例 10-2,#define N 10#include main()int RN+1,i,j;int flag=1;for(i=1;i=N;i+)scanf(%d,for(j=1;jRj+1)flag=1;R0=Rj;Rj=Rj+1;Rj+1=R0;for(i=1;i=N;i+)printf(%d,Ri);,程序如下：,10.3.2 快速排序,任意选取记录序列中的一个记录作为基准记录Ri（一般可取第一个记录R1），把它和所有待排序记录比较，将所有比它小的记录都置于它之前，将所有比它大的记录置于它之后，这一个过程称为一趟快速排序。经一趟快速排序后，将待排序记录序列划分成左右两部分，然后分别对这两部分重复上述过程进行排序，直到每一部分的记录个数为1为止。,快速排序的基本思想,已知一关键字序列（33，85，64，15，73，56，42，20），请给出采用快速排序的方法对这8个数按升序排序时的第一趟排序的过程。,例,设两个指针i、j分别指向无序区的第一个和最后一个记录的位置，选取区域第一个记录R1作为基准记录。从区域右端开始，自右向左逐个记录依次和R1比较，当某个记录比R1小时，把该记录移到左端，然后从区域的左端开始，自左向右逐个记录依次和R1比较，当某个记录比R1大时，把该记录移到右端；又从右端第一个未比较的记录开始重复上述步骤，直到R1与无序区中的所有记录都比较过。,快速排序的实现方法,写出对下列一组数（56 23 30 78 90 65 42 86）进行快速排序时，每一趟排序的状态。快速排序的每一趟结果为：,例 10-3,初始状态：56 23 30 78 90 65 42 86第一趟排序后：42 23 30 56 90 65 78 86第二趟排序后：30 23 42 56 86 65 78 90第三趟排序后：23 30 42 56 78 65 86 90第四趟排序后：23 30 42 56 65 78 86 90结果为：23 30 42 56 65 78 86 90,quicksort.c,时间复杂度：平均情况，快速排序的时间复杂度为(nlog2n)。空间复杂度：从所需的附加空间来看，(log2n)。稳定性：从排序的稳定性来看，快速排序是不稳定的。,快速排序算法的性能,10.4 选择排序,选择排序是不断的从待排序的记录序列中选取关键字最小的记录，依次放到已排好序的子序列的最后，直到全部记录排好序。最常用选择排序有简单选择排序和堆排序。,第一趟从所有的n个记录中，通过顺序比较各关键字的值，选取关键字值最小的记录与第一个记录交换；第二趟从剩余的n-1个记录中选取关键字值最小的记录与第二个记录交换；，第i趟从剩余的n-i+1个记录中选取关键字值最小的记录，与第i个记录交换；经过n-1趟排序后，整个序列就成为有序序列。,简单选择排序的基本思想,初始关键字：33 85 64 15 73 56 42 20第一趟排序后：15 85 64 33 73 56 42 20第二趟排序后：15 20 64 33 73 56 42 85第三趟排序后：15 20 33 64 73 56 42 85第四趟排序后：15 20 33 42 73 56 64 85第五趟排序后：15 20 33 42 56 73 64 85第六趟排序后：15 20 33 42 56 64 73 85第七趟排序后：15 20 33 42 56 64 73 85 最后结果：15 20 33 42 56 64 73 85,例：对33、85、64、15、73、56、42、20关键字序列，用简单选择排序法排序的过程如下图所示。假设为有序区，为无序区。,void selectionsort(int R,int n)int i,j,k;for(i=1;i=n-1;i+)k=i;for(j=i+1;j=n;j+)if(RjRk)k=j;if(i!=k)R0=Rk;Rk=Ri;Ri=R0;,简单选择排序的算法,时间复杂度：简单选择排序的时间复杂度为O（n2）。空间复杂度：从所需的附加空间来看，其空间复杂度为O（1）。稳定性：从排序的稳定性来看，简单选择排序是不稳定的。,简单选择排序算法的性能,从键盘上输入n个数，要求用简单选择排序算法对这n个数按由大到小的顺序排序并输出。程序如下：,#define N 15void selectionsort(int R,int n);main()int i,aN+1;for(i=1;i=N;i+)scanf(%d,void selectionsort(int R,int n)int i,j,k;for(i=1;iRk)k=j;if(i!=k)R0=Rk;Rk=Ri;Ri=R0;,例 10-4,10.5 归并排序,将初始的n个待排序记录，看成是n个长度为1的有序子序列，从第1个子序列开始两两归并，得到n/2个有序子序列。我们把这一个过程称为一趟归并排序。然后再对n/2个有序子序列进行两两归并，如此重复，直到得到一个长度为n的有序序列为止。,由于在归并排序的过程中子序列总是两两归并的，所以把这种排序方法称为2-路归并排序。2-路归并排序的核心是如何将相邻的两个有序序列归并成一个有序序列。,归并排序的基本思想,初始关键字 20 51 70 33 15 48 62 第一趟归并后 20 51 33 70 15 48 62 第二趟归并后 20 33 51 70 15 48 62最后一趟归并结果 15 20 33 48 51 62 70,例：一个2-路归并排序过程示意图。,时间复杂度：归并排序的时间复杂度为O（nlog2n）。空间复杂度：归并排序需要和待排序记录相等数量的辅助空间，所以归并排序的空间复杂度为O（n）。稳定性：在归并排序过程中的主要操作是有秩序的复制记录，因此它是一种稳定的排序方法。,2-路归并排序的算法性能,10.6 各种内排序算法的比较,本章所讨论的排序算法都是在顺序存储结构上实现的，所有的排序算法都需要通过关键字比较和记录移动来完成排序。每一种排序算法的时间和空间复杂度及稳定性各不相同。本章中主要内部排序算法的性能比较如下表所示：,（1）就平均时间性能而言，快速排序和归并排序有最好的时间性能。相对而言，快速排序速度最快。但快速排序在最坏情况下的时间性能达到了O（n2），不如归并排序。（2）就空间性能来看，直接插入排序、折半插入排序、冒泡排序、简单选择排序要求的辅助空间较小，但时间性能较差。（3）从稳定性来看，除快速排序和简单选择排序是不稳定的外，其他的几种排序方法都是稳定的。（4）另外，从待排序记录的个数来看，当待排序记录的个数较少时，采用直接插入排序、折半插入排序或简单选择排序较好；当待排序记录的个数较多时，采用快速排序或归并排序较合适。,结论：,10.7 内排序算法举例,已知一关键字序列（503，87，512，908，170，276，436，316），请给出采用下列算法对该序列按升序排序时的每一趟的排序结果。（1）直接插入排序；（2）冒泡排序；（3）快速排序；（4）简单选择排序；（5）归并排序。,例 10-5,（1）直接插入排序各趟排序的结果为：,初始关键字：503 87 512 908 170 276 436 316第一趟排序：87 503 512 908 170 276 436 316第二趟排序：87 503 512 908 170 276 436 316第三趟排序：87 503 512 908 170 276 436 316第四趟排序：87 170 503 512 908 276 436 316第五趟排序：87 170 276 503 512 908 436 316第六趟排序：87 170 276 436 503 512 908 316第七趟排序：87 170 276 316 436 503 512 908,（2）冒泡排序各趟排序的结果为：,初始关键字：503 87 512 908 170 276 436 316第一趟排序：87 503 512 170 276 436 316 908第二趟排序：87 503 170 276 436 316 512 908第三趟排序：87 170 276 436 316 503 512 908第四趟排序：87 170 276 316 436 503 512 908第五趟排序：87 170 276 316 436 503 512 908,例 10-5续,（3）快速排序各趟排序的结果为：,初始关键字：503 87 512 908 170 276 436 316第一趟排序：316 87 436 276 170 503 908 512 第二趟排序：170 87 276 316 436 503 512 908第三趟排序：87 170 276 316 436 503 512 908最后结果：87 170 276 316 436 503 512 908,（4）简单选择排序各趟排序的结果为：,初始关键字：503 87 512 908 170 276 436 316第一趟排序：87 503 512 908 170 276 436 316第二趟排序：87 170 512 908 503 276 436 316第三趟排序：87 170 276 908 503 512 436 316第四趟排序：87 170 276 316 503 512 436 908 第五趟排序：87 170 276 316 436 512 503 908第六趟排序：87 170 276 316 436 503 512 908第七趟排序：87 170 276 316 436 503 512 908,例 10-5续,（5）归并排序的各趟排序结果为：,初始关键字：503 87 512 908 170 276 436 316第一趟排序：87 503 512 908 170 276 316 436第二趟排序：87 503 512 908 170 276 316 436第三趟排序：87 170 276 316 503 512 436 908,例 10-5续,排序是程序设计和数据处理中常用的一种运算。本章介绍了插入排序、交换排序、选择排序、归并排序等四类内部排序算法，每类排序中又介绍了最常用的几种算法，包括排序方法的基本思想、排序过程及算法实现，并简要分析了算法的时间复杂度和空间复杂度。要求理解各种内部排序方法的基本思想和特点，熟悉各种内部排序的过程，并掌握2-3种排序方法的算法，记住各种排序方法的时间复杂度和空间复杂度。,本章小结,作业,已知一关键字序列（78，35，12，26，90，41，66，58），请给出采用下列算法对该序列按升序排序时的第一趟后的排序结果。（1）直接插入排序；（2）冒泡排序；（3）快速排序；（4）简单选择排序；（5）归并排序。,