常见三种排序方法PPT参考课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,C Programming Language,#,数组操作,（,1,）选择排序法,（,2,）冒泡排序法,（,3,）比较排序法,（,1,）顺序查找法,（,2,）折半查找法,（,1,）数组元素插入,（,2,）数组元素删除,（,1,）,选择排序,第,17,、,26,套的填空题,简单选择排序,:,从,1,到,n,选出,关键值最（大）小,的记录，交换到,第一个位置,上，然后从,2,到,n,选 出键值最（大）小的记录，交换到第 二个位置上，,.,54 71 58 29 31,54 71 58 29 31,54 71 58 29 31,54,71 58,29,31,i=0,初态,k=0,数组下标,0 1 2 3 4,j=1,k=0,j=2,k=0,j=3,k=3,j=4,k!=i,交换,第一趟,互换,i=0,判断,ajak?,用选择法对数组,int a5=54,71,58,29,31,进行,升序排序,k=j,k=1,j=2,i=1,29,71 58 54 31,j=3,k=2,i=1,第二趟,29,71 58 54 31,29,71 58 54 31,i=1,k=3,j=4,29,71 58 54 31,i=1,k=4,k!=i,交换,互换,29,31,58 54 71,判断,ajak?,k=j,k=j,k=j,29,31,58 54 71,i=2,k=2,j=3,29,31,58,54,71,i=2,k=3,j=4,29,31,54,58 71,互换,第三趟,k!=i,交换,i=3,k=3,j=4,k=i,不交换,第四趟,判断,ajak?,“,选择排序法,”,（由小到大排序）,选择法,(,递增,),基本思想：,(1),从,n,个数的序列中选出最小的数，与第,1,个数交换位置；,(2),除第,1,个数外，其余,n,-1,个数再按,(1),的方法选出次小的数，与第,2,个数交换位置,;,(3),重复,(1),n,-1,遍，最后构成递增序列。,实现方法：,采用双重循环（循环的嵌套）,外循环为,i,：控制,排序趟数,内循环为,j,：第,i,趟排序过程中的,下标变量,“,选择”排序法的结构形式：,for(i=0;in-1;i+),k=i,;,for(j=i+1;jaj),k=j,;,if(,k!=i,),t=ai;ai=ak;ak=t;,K,是记下最值的下标,K,不在本次排序中的位置,#include,#include stdlib.h,void main(),const int N=10;,int i,j,k,t,aN;,for(i=0;i N;i+),ai=rand()%61;,printf(%d,ai);,printf(n);,for(i=0;i N-1;i+),k=i;,for(j=i+1;j aj)k=j;,if(k!=i)t=ak;ak=ai;ai=t;,for(i=0;iN;i+)printf(%5d,ai);,printf(n);,第二种：“冒泡法”,（由小到大排序）,基本思想：,(1),从第一个元素开始，对数组中两两相邻的元素比较，将值较小的元素放在前面，值较大的元素放在后面，一轮比较完毕，最大的数存放在,aN-1,中；,(2),然后对,a0,到,aN-2,的,N-1,个数进行同（,1,）的操作，次最大数放入,aN-2,元素内，完成第二趟排序；依次类推，进行,N-1,趟排序后，所有数均有序。,实现方法：,采用双重循环（循环的嵌套）,49,36,41,65,11,第,六,趟,排,序,后,第,五,趟,排,序,后,第,四,趟,排,序,后,第,三,趟,排,序,后,第,二,趟,排,序,后,第,一,趟,排,序,后,初,始,关,键,字,78,36,65,36,41,56,36,41,65,41,36,41,56,11,78,36,36,41,49,11,56,49,25,25,25,11,49,49,56,11,11,11,25,25,25,25,（,2,）冒泡排序,交换排序：,俩俩比较待排序记录的键值，若逆序，则交换，直到全部满足为止,交 换 排 序,“,冒泡”排序法,特点：逐个对数组中每相邻二数进行比较，若条件满 足，则互相交换，否则保持原位置不变。,千万要注意！,若有,n,个数据，需要进行,i=,n-1,轮比较。每轮中比较的次数为,j=n-i+1,次。,排序过程：（设数据存于,A,数组中，,n,个数据，按递增,次序排序）,A0,与,A1,比较,A0A(1),不换，否则对调,A1,与,A2,比较,A1A2,不换，否则对调,：,An-2,与,An-1,比较,An-2An-1,不换，否则对调,冒泡法排序,用冒泡法对,10,个数排序,(,由小到大,),。,4,8,2,7,5,9,2,4,8,5,7,9,2,4,5,8,7,9,2,4,5,7,8,9,2,4,5,7,8,9,2,4,5,7,8,9,冒泡排序的,结构形式,（递增）,for(i=0;iN-1;i+),for(j=0;jaj+1)t=aj;aj=aj+1;aj+1=t;,for(i=,1,;i,n,;i+),for(j=0,;ja,j+1,)t=aj;aj=aj+1;aj+1=t;,关键代码：,14,for(i=,0,;i,n,-1,;i+),for(j=0 ;ja,j+1,)t=aj;aj=aj+1;aj+1=t;,注意排序堂数,i,的初值,注意,i,的边界,注意,j,的边界,#include ,#define N 6,void main(),int i,j,t,aN;,printf(input N numbers:n);,for(i=0;iN;i+),scanf(%d,printf(n);,for(i=0;i,N-1,;i+),for(j=0;jaj+1),t=aj;aj=aj+1;aj+1=t;,for(i=0;iN;i+)printf(%5d,ai);,printf(n);,冒泡程序,第三种：比较排序,（上机,19,、,52,套编程题）,for(i=,0,;i,n,-1,;i+),for(j=i+1 ;ja,j,)t=ai;ai=aj;aj=t;,注意排序堂数,i,的初值,注意,i,的边界,注意,j,的边界,注意,ai,与,aj,比较,补充知识一：查找,查找的方法很多。,如：,顺序查找、二分法查找,等等。,1,、顺序查找：,最简单的查找方法，基本思想是利用循环顺序扫描整个数组，依次将每个元素与待查找值比较，直至找到或找不到。,对于无序数组，顺序查找是唯一可行的办法,对大批量数据用顺序查找占机器时间较多。,int,Search(,long,a,int,n,long,x),int,i;,for,(i=0;in;i+),if,(ai=x),return,(i);,return,(-1);,2,、二分法查找,/,折半查找：,二分法查找的条件：,必须是有序数列，即数组中的各元素已按数值大小按递增或递减次序排列！,查找过程：,(1),将数列对分，找出中间数据,(2),用此数据与要查的数据比较,(3),数值相等则结束查询，否则确定要查的数据所在区间，逐步缩小查找范围，每次将数列区间缩小一半，直到找到或找不到为止。,(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),low,mid,(08,14,23,37,46,55,68,79,91),low,mid,mid,low,mid,mid,low,high=mid-1,high,high,high,折半查找（二分法查找）,high,low,(08,14,23,37,46,55,68,79,91),mid,low,high,下标,0 1 2 3 4 5 6 7 8,折半查找,1,，,5,，,6,，,9,，,11,，,17,，,25,，,34,，,38,，,41,下界,low,上界,up,中值,mid,共有,10,个已排好序的数据：查找,9,。,up=9 low=0,mid=(up+low)/2=4,查找范围：,up=3 low=0,mid=(up+low)/2=1,up=3 low=2,mid=(up+low)/2=2,up=3 low=3,mid=(up+low)/2=3,int,BinSearch(,long,a,int,n,long,x),int,low,high,mid;,low=0;,high=n-1;,while,(,low amid),low=mid+1;,else,if,(x=low&,!found,),mid=(up+low)/2;,if(amid=find)found=1;break;,else if(amidfind)up=mid-1;,else low=mid+1;,if(found)printf(found number is%dth mid);,else printf(no found);,补充知识二：数组元素的插入、删除,1,、插入数据,在有序数组中插入数据后，数组仍然有序。,要求数组有足够的空间。,前提：被操作数组已经是有序数组，操作前后不改变数组的有序性,插入过程：,(1),确定数据插入位置,(2),从最后一个元素开始逐个后移，直到将第,i,个位置腾出。,(ai+1=ai),(3),将数据插入到指定下标元素位置中,插入运算,a,i-1,.,a,1,a,0,a,length,a,i+1,a,i,x,a,i-1,.,a,1,a,0,a,i,a,i+1,a,length,a,length,a,i+1,a,i,x,2,、删除数据,在有序的数组中删除数据后，数组仍然有序。,删除过程：,(1),确定数据删除位置,i,(2),从第,i,1,个位置开始逐个向前移动,原数组元素,，,(ai=ai+1),下面介绍,引用一维数组元素,的三种方式。,1.,下标方式,形式：,数组名,下标,如,ai,2.,地址方式,形式：,*（地址）,如*,(a+i),等价,ai,3.,指针方式,形式：,*指针变量名,如,:,int a10,*p,；,p=&ai,*p=ai;,一维数组与指针,1,数组,就是,连续存放,的若干元素的集合。,2,数组名,就是指向数组第一个元素的,首地址（指针）,如,int a10,*p,；则,p=a,等价于,p=&a0,；,3,某一元素的地址：,p=&ai,，则用指针引用该元素为：*,p=ai;,4,数组元素下标在内部实现时，统一按“基地址位移”的方式处理。即：,a,，,a,1,，,a,i,；,表示数组的地址可用：,p+i,，,a+i,表示数组的内容可用：,ai,，*,(p+i),，*,(a+i),注意：,虽然,a,与,p,都可以指示地址，但,a,是指,首地址,，,p,是,变量,（可以指首地址，也可以指其他地址）,