数据排序(C版)素材课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 数据排序,信息获取后通常需要进行处理，处理后的信息其目的是便于人们的应用。信息处理方法有多种，通常有数据的排序，查找，插入，删除，归并等操作。读者已经接触了一些这方面的知识，本章重点介绍数据排序的几种方法。,1.,选择排序,（,1,）基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在待排序的数列的最前，直到全部待排序的数据元素排完。（,2,）排序过程：,【,示例,】,：,初 始 关键字,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,最后排序结果,13 27 38 49 49 65 76 97,void SelectSort(int R)/,对,R1.N,进行直接选择排序,for(int i=1;i=n-1;i+)/,做,N-1,趟选择排序,K=I;,For(int j=i+1;j=n;j+)/,在当前无序区,RI.N,中选最小的元素,RK,If(RJ RK)K=J;,If(K!=I)/,交换,RI,和,RK,Temp=RI;,RI=RK;,RK=Temp;,/SelectSort,2.,冒泡排序,（,1,）基本的冒泡排序,基本思想,依次比较相邻的两个数，把大的放前面，小的放后面。即首先比较第,1,个数和第,2,个数，大数放前,小数放后。然后比较第,2,个数和第,3,个数,.,直到比较最后两个数。第一趟结束，最小的一定沉到最后。重复上过程,仍从第,1,个数开始,到最后第,2,个数，然后,.,由于在排序过程中总是大数往前，小数往后，相当气泡上升，所以叫冒泡排序。,下面是,6,个元素的排序的过程,4 5 7 1 2 3,5 4 7 1 2 3,5 7 4 1 2 3,5 7 4 1 2 3,5 7 4 2 1 3,第一趟结束,5 7 4 2 3,7 5 4 2 3 1,7 5 4 2 3 1,7 5 4 2 3 1,第二趟结束,7 5 4 3 1,7 5 4 3 2 1,7 5 4 3 2 1,第三趟结束,7 5 4 2 1,7 5 4 3 2 1,第四趟结束,7 5 3 2 1,第五趟结束,4 3 2 1,算法实现,for(int i=1;i=n-1;i+),for(int j=1;j=n-i;j+),if(ajaj+1),temp=aj;aj=aj+1;aj+1=temp;,（,2,）改进,上例中，可以发现，第二趟结束已经排好序。但是计算机此时并不知道已经排好序。所以，还需进行一次比较，如果没有发生任何数据交换，则知道已经排好序，可以不干了。因此第三趟比较还需进行，第四趟、第五趟比较则不必要。,我们设置一个布尔变量,bo,来记录是否有进行交换。值为,false,表示本趟中进行了交换，,true,则没有。代码如下,:,int i=1;,do,bo=true;,for(int j=1;j=n-i;j+),if(ajn;,for(i=1;ik;bk+;/,将关键字等于,k,的值全部装入第,k,桶,for(i=0;i0)couti ;bi-;/,输出排序结果,coutendl;,4.,插入排序,插入排序是一种简单的排序方法，其算法的基本思想是：,假设待排序的数据存放在数组,R1.n,中，增加一个哨兵结点,x,。,(1)R1,自成,1,个有序区，无序区为,R2.n;(2),从,i=2,起直至,i=n,为止，将,Ri,放在恰当的位置，使,R1.i,数据序列有序,;,x:=Ri;,将,x,与前,i-1,个数比较,j:=i-1;while xaj do j:=j-1;,将,R,数组的元素从,j,位置开始向后移动,:for k:=i downto j do ak:=ak-1;,Rj=x;,(3),生成包含,n,个数据的有序区。,.,例如,:,设,n=8,，数组,R,中,8,个元素是,:36,25,48,12,65,43,20,58,，执行插入排序程序后，其数据变动情况：,第,0,步,:36 25 48 12 65 43 20 58,第,1,步,:,25,36 48 12 65 43 20 58,第,2,步,:25 36,48,12 65 43 20 58,第,3,步,:,12,25 36 48 65 43 20 58,第,4,步,:12 25 36 48,65,43 20 58,第,5,步,:12 25 36,43,48 65 20 58,第,6,步,:12,20,25 36 43 48 65 58,第,7,步,:12 20 25 36 43 48,58,65,该算法的程序简单，读者自己完成。其算法的时间复杂性为,O(n,2,),插入排序适用于原先数据已经排列好，插入一个新数据的情况。,void insertsort(int r)/,对,r1.n,按递增序进行插入排序，,x,是监视哨,for(i=2;i=n;i+)/,依次插入,r2,.,rn,x=ri;,j=i-1;,while(xj,为止。,快速排序的时间的复杂性是,O(nlog2n),，速度快,但它是不稳定的排序方法。就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法,由以上讨论可知，从时间上看，快速排序的平均性能优于前面讨论过的各种排序方法，但快速排序需一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度相接近的两个子序列，则栈的最大深度为,log(n+1),。,快速排序算法,void qsort(int l,int r),int i,j,mid,p;,i=l;,j=r;,mid=a(l+r)/2;/,将当前序列在中间位置的数定义为分隔数,do,while(aimid)j-;/,在右半部分寻找比中间数小的数,if(i=j),/,若找到一组与排序目标不一致的数对则交换它们,p=ai;,ai=aj;,aj=p;,i+;,j-;/,继续找,while(i=j);/,注意这里不能有等号,if(lj)qsort(l,j);/,若未到两个数的边界，则递归搜索左右区间,if(ir)qsort(i,r);,6.,归并排序,将两个或两个以上有序的数列,(,或有序表,),，合并成一个仍然有序的数列,(,有序表,),，这种操作称为归并操作。这样的方法经常用于多个有序的数据文件归并成一个有序的数据文件。若将两个有序表合并成一个有序表则称为二路归并，同理，有三路归并、四路归并等。二路归并比较简单，所以我们只讨论二路归并。例如有两个有序表,:(7,，,10,，,13,，,15),和,(4,，,8,，,19,，,20),，归并后得到的有序表为,:(4,，,7,，,8,，,10,，,13,，,15,，,19,，,20),。,归并过程为,:,比较,Ai,和,Aj,的大小，若,AiAj,，则将第一个有序表中的元素,Ai,复制到,Rk,中，并令,i,和,k,分别加,1,，即使之分别指问后一单元，否则将第二个有序表中的元素,Aj,复制到,Rk,中，并令,j,和,k,分别加,1;,如此循环下去，直到其中的一个有序表取完,然后再将另一个有序表中剩余的元素复制到,R,中从下标,k,到下标,t,的单元,.,二路归并算法描述为,(As,t,中的数据由小到大合并到,Rs,t,中,):,void merge(int s,int m,int t),/,两个有序表,As,m,和,Am+1,t,合并成一个有序表,Rs,t,/s,是第一个有序表起点位置，,m+1,是第二个有序表的起点,i=s;,j=m+1;,k=s;/i,和,j,分别指向二个有序表的头部,while(i=m&j=t),if(Ai=Aj),Rk=Ai;i+;k+;,else Rk=Aj;j+;k+;,while(i=m)Rk=Ai;i+;k+;/,复制第一路剩余,while(j=t)Rk=Aj;j+;k+;/,复制第二路剩余,归并排序,(Merge sort),就是利用归并操作把一个无序表排列成一个有序表的过程。二路归并排序的过程是首先把待排序区间（即无序表）中的每一个元素都看作为一个有序表，则,n,个元素构成,n,个有序表，接着两两归并（即第一个表同第二个表归并，第三个表同第四个表归并，,），得到,n/2,个长度为,2,的有序表（最后一个表的长度可能小于,2,），称此为一趟归并，然后再两两有序表归并，得到,n/2/2,个长度为,4,的有序表（最后一个表的长度可能小于,4,），如此进行下去，直到归并第,log2n,趟后得到一个长度为,n,的有序表为止。,归并排序算法我们用递归实现，先把待排序区间,s,t,以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间,s,t,。对左右子区间的排序与原问题一样，所以我们可以调用同样的子程序，只是区间大小不一样。,归并排序程序如下：,program ex_2;,#include,using namespace std;,int a10001,r10001,n,i;/a,是待排序数组，,r,是临时数组,void mergesort(int s,int t)/,对,s,t,区间的无序数据进行归并排序,int m,i,j,k;,if(s=t)return;/,若区间只有一个数据就不用排了,m=(s+t)/2;/,取区间的中点,mergesort(s,m);/,以中点二分，对左边了区间进行排序,mergesort(m+1,t);/,以中点二分，对右边了区间进行排序,i=s;/,以下是一次归并（合并）操作,j=m+1;,k=s;,while(i=m&j=t)do /,二个子序列从小大到合并，直到有一列结束,if(ai=aj),rk=ai;i+;k+;,else,rk=aj;j+;k+;,while(i=m)/*,把左边子序列剩余的元素接入进来*,rk=ai;i+;k+;,while(j=t)/,把右边子序列剩余的元素接入进来,rk=aj;j+;k+;,for(i=s;in;,for(i=1;iai;,mergesort(1,n);/,对,1,n,区间的无序数据进行归并排序,for(i=1;i=n;i+)/,输出,n,个有序的数据,coutai ;,coutendl;,7.,各种排序算法的比较,1.,稳定性比较,插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的。,选择排序、希尔排序、快速排序、堆排序是不稳定的。,2.,时间复杂性比较,插入排序、冒泡排序、选择排序的时间复杂性为,O(n2),；快速排序、堆排序、归并排序的时间复杂性为,O(nlog2n),；桶排序的时间复杂性为,O(n);,若从最好情况考虑，则直接插入排序和冒泡排序的时间复杂度最好，为,O(n),，其它算法的最好情况同平均情况相同；若从最坏情况考虑，则快速排序的时间复杂度为,O(n2),，直接插入排序和冒泡排序虽然平均情况相同，但系数大约增加一倍，所以运行速度将降低一半，最坏情况对直接选择排序、堆排序和归并排序影响不大。,由此可知，在最好情况下，直接插入排序和冒泡排序最快；在平均情况下，快速排序最快；在最坏情况下，堆排序和归并排序最快。,3.,辅助空间的比较,桶排序、二路归并排序的辅助空间为,O(n),，快速排序的辅助空间为,O(log2n),，最坏情况为,O(n),，其它排