常见三种排序方法课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,C Programming Language,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,C Programming Language,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数组操作,（,1,）选择排序法,（,2,）冒泡排序法,（,3,）比较排序法,（,1,）顺序查找法,（,2,）折半查找法,（,1,）数组元素插入,（,2,）数组元素删除,数组操作（1）选择排序法（1）顺序查找法（1）数组元素插入,（,1,）,选择排序,第,17,、,26,套的填空题,简单选择排序,:,从,1,到,n,选出关键值最（大）小的记录，交换到第一个位置上，然后从,2,到,n,选 出键值最（大）小的记录，交换到第 二个位置上，,.,（1）选择排序第17、26套的填空题简单选择排序:,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,54 71 58 29 31i=0初,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,k=1j=2i=1 29 71 58 54,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?,29 31 58 54 71i=2k=,“,选择排序法”,（由小到大排序）,选择法,(,递增,),基本思想：,(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;,“选择”排序法的结构形式：for(i=0;in-1;i+,#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);,#include,第二种：“冒泡法”,（由小到大排序）,基本思想：,(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,）冒泡排序,交换排序：俩俩比较待排序记录的键值，若逆序，则交换，直到全部满足为止,4936416511第第第第第第初7836653641563,交 换 排 序,“,冒泡”排序法,特点：逐个对数组中每相邻二数进行比较，若条件满 足，则互相交换，否则保持原位置不变。,千万要注意！,若有,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,冒泡法排序用冒泡法对10个数排序(由小到大)。422222,冒泡排序的结构形式（递增）,for(i=0;iN-1;i+),for(j=0;jaj+1)t=aj;aj=aj+1;aj+1=t;,冒泡排序的结构形式（递增）for(i=0;iN-1;i+,for(i=1;i n;i+),for(j=0,;jaj+1)t=aj;aj=aj+1;aj+1=t;,关键代码：,14,for(i=0 ;i n-1 ;i+),for(j=0 ;jaj+1)t=aj;aj=aj+1;aj+1=t;,for(i=1;i n;i+)关键代,#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;iN-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);,冒泡程序,#include 冒泡程序,第三种：比较排序,（上机,19,、,52,套编程题）,for(i=0 ;i n-1 ;i+),for(j=i+1 ;jaj)t=ai;ai=aj;aj=t;,注意,ai,与,aj,比较,第三种：比较排序（上机19、52套编程题）for(i=,补充知识一：查找,查找的方法很多。,如：顺序查找、二分法查找等等。,1,、顺序查找：,最简单的查找方法，基本思想是利用循环顺序扫描整个数组，依次将每个元素与待查找值比较，直至找到或找不到。,补充知识一：查找查找的方法很多。1、顺序查找：,对于无序数组，顺序查找是唯一可行的办法,对大批量数据用顺序查找占机器时间较多。,int Search(long a,int n,long x),int i;,for(i=0;in;i+),if(ai=x),return(i);,return(-1);,对于无序数组，顺序查找是唯一可行的办法int Search,2,、二分法查找,/,折半查找：,二分法查找的条件：,必须是有序数列，即数组中的各元素已按数值大小按递增或递减次序排列！,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,(08,14,23,折半查找,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,折半查找1，5，6，9，11，17，25，34，38，41下,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);,折半查找程序#include ,补充知识二：数组元素的插入、删除,1,、插入数据,在有序数组中插入数据后，数组仍然有序。,要求数组有足够的空间。,前提：被操作数组已经是有序数组，操作前后不改变数组的有序性,补充知识二：数组元素的插入、删除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,插入运算ai-1.a1a0alength ai,2,、删除数据,在有序的数组中删除数据后，数组仍然有序。,删除过程：,(1),确定数据删除位置,i,(2),从第,i,1,个位置开始逐个向前移动原数组元素，,(ai=ai+1),2、删除数据删除过程：,下面介绍引用一维数组元素的三种方式。,1.,下标方式,形式：数组名,下标,如,ai,2.,地址方式,形式：,*（地址）,如*,(a+i),等价,ai,3.,指针方式,形式：,*指针变量名,如,:,int a10,*p,；,p=,下面介绍引用一维数组元素的三种方式。,一维数组与指针,1,数组就是连续存放的若干元素的集合。,2,数组名就是指向数组第一个元素的首地址（指针）,如,int a10,*p,；则,p=a,等价于,p=&a0,；,3,某一元素的地址：,p=&ai,，则用指针引用该元素为：