常见三种排序方法

CProgrammingLanguage1数组操作（1）选择排序法（2）冒泡排序法（3）比较排序法（1）顺序查找法（2）折半查找法（1）数组元素插入（2）数组元素删除CProgrammingLanguage2（1）选择排序——第17、26套的填空题简单选择排序:从1到n选出关键值最（大）小的记录，交换到第一个位置上，然后从2到n选出键值最（大）小的记录，交换到第二个位置上，….CProgrammingLanguage35471582931547158293154715829315471582931i=0初态k=0数组下标01234j=1k=0j=2k=0j=3k=3j=4k!=i,交换第一趟互换i=0判断a[j]a[k]?用选择法对数组inta[5]={54,71,58,29,31}进行升序排序k=jCProgrammingLanguage4k=1j=2i=12971585431j=3k=2i=1第二趟29715854312971585431i=1k=3j=42971585431i=1k=4k!=i,交换互换2931585471判断a[j]a[k]?k=jk=jk=jCProgrammingLanguage52931585471i=2k=2j=32931585471i=2k=3j=42931545871互换第三趟k!=i,交换i=3k=3j=4k=i,不交换第四趟判断a[j]a[k]?CProgrammingLanguage6“选择排序法”（由小到大排序）选择法(递增)基本思想：(1)从n个数的序列中选出最小的数，与第1个数交换位置；(2)除第1个数外，其余n-1个数再按(1)的方法选出次小的数，与第2个数交换位置;(3)重复(1)n-1遍，最后构成递增序列。实现方法：采用双重循环（循环的嵌套）外循环为i：控制排序趟数内循环为j：第i趟排序过程中的下标变量CProgrammingLanguage7“选择”排序法的结构形式：for(i=0;in-1;i++){k=i;for(j=i+1;jn;j++)if(a[k]a[j])k=j;if(k!=i){t=a[i];a[i]=a[k];a[k]=t;}}K是记下最值的下标K不在本次排序中的位置CProgrammingLanguage8#includestdio.h#includestdlib.hvoidmain(){constintN=10;inti,j,k,t,a[N];for(i=0;iN;i++){a[i]=rand()%61;printf(%d,,a[i]);}printf(\n);for(i=0;iN-1;i++){k=i;for(j=i+1;jN;j++)if(a[k]a[j])k=j;if(k!=i){t=a[k];a[k]=a[i];a[i]=t;}}for(i=0;iN;i++)printf(%5d,a[i]);printf(\n);}CProgrammingLanguage9第二种：“冒泡法”（由小到大排序）基本思想：(1)从第一个元素开始，对数组中两两相邻的元素比较，将值较小的元素放在前面，值较大的元素放在后面，一轮比较完毕，最大的数存放在a[N-1]中；(2)然后对a[0]到a[N-2]的N-1个数进行同（1）的操作，次最大数放入a[N-2]元素内，完成第二趟排序；依次类推，进行N-1趟排序后，所有数均有序。实现方法：采用双重循环（循环的嵌套）CProgrammingLanguage104936416511第六趟排序后第五趟排序后第四趟排序后第三趟排序后第二趟排序后第一趟排序后初始关键字783665364156364165413641561178363641491156492525251149495611111125252525（2）冒泡排序交换排序：俩俩比较待排序记录的键值，若逆序，则交换，直到全部满足为止CProgrammingLanguage11交换排序——“冒泡”排序法特点：逐个对数组中每相邻二数进行比较，若条件满足，则互相交换，否则保持原位置不变。千万要注意！！若有n个数据，需要进行i=n-1轮比较。每轮中比较的次数为j=n-i+1次。排序过程：（设数据存于A数组中，n个数据，按递增次序排序）A[0]与A[1]比较A[0]A(1)不换，否则对调A[1]与A[2]比较A[1]A[2]不换，否则对调：A[n-2]与A[n-1]比较A[n-2]A[n-1]不换，否则对调CProgrammingLanguage12冒泡法排序用冒泡法对10个数排序(由小到大)。482759248579245879245789245789245789CProgrammingLanguage13冒泡排序的结构形式（递增）for(i=0;iN-1;i++)for(j=0;jN-i-1;j++)if(a[j]a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}CProgrammingLanguage14for(i=1;in;i++)for(j=0;jn-i;j++)if(a[j]a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}关键代码：14for(i=0;in-1;i++)for(j=0;jn-i-1;j++)if(a[j]a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}注意排序堂数i的初值注意i的边界注意j的边界CProgrammingLanguage15#includestdio.h#defineN6voidmain(){inti,j,t,a[N];printf(inputNnumbers:\n);for(i=0;iN;i++)scanf(%d,&a[i]);printf(\n);for(i=0;iN-1;i++)for(j=0;jN-i-1;j++)if(a[j]a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}for(i=0;iN;i++)printf(%5d,,a[i]);printf(\n);}冒泡程序CProgrammingLanguage16第三种：比较排序（上机19、52套编程题）for(i=0;in-1;i++)for(j=i+1;jn;j++)if(a[i]a[j]){t=a[i];a[i]=a[j];a[j]=t;}注意排序堂数i的初值注意i的边界注意j的边界注意a[i]与a[j]比较CProgrammingLanguage17补充知识一：查找查找的方法很多。如：顺序查找、二分法查找等等。1、顺序查找：最简单的查找方法，基本思想是利用循环顺序扫描整个数组，依次将每个元素与待查找值比较，直至找到或找不到。CProgrammingLanguage18•对于无序数组，顺序查找是唯一可行的办法•对大批量数据用顺序查找占机器时间较多。intSearch(longa[],intn,longx){inti;for(i=0;in;i++){if(a[i]==x){return(i);}}return(-1);}CProgrammingLanguage192、二分法查找/折半查找：二分法查找的条件：必须是有序数列，即数组中的各元素已按数值大小按递增或递减次序排列！CProgrammingLanguage20查找过程：(1)将数列对分，找出中间数据(2)用此数据与要查的数据比较(3)数值相等则结束查询，否则确定要查的数据所在区间，逐步缩小查找范围，每次将数列区间缩小一半，直到找到或找不到为止。CProgrammingLanguage21(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)lowmid(08,14,23,37,46,55,68,79,91)lowmidmidlowmidmidlowhigh=mid-1highhighhigh折半查找（二分法查找）highlow(08,14,23,37,46,55,68,79,91)midlowhigh下标012345678CProgrammingLanguage22折半查找1，5，6，9，11，17，25，34，38，41下界low上界up中值mid共有10个已排好序的数据：查找9。up=9low=0mid=(up+low)/2=4查找范围：up=3low=0mid=(up+low)/2=1up=3low=2mid=(up+low)/2=2up=3low=3mid=(up+low)/2=3CProgrammingLanguage23intBinSearch(longa[],intn,longx){intlow,high,mid;low=0;high=n-1;while(low=high){mid=(high+low)/2;if(xa[mid]){low=mid+1;}elseif(xa[mid]){high=mid-1;}else{return(mid);}}return(-1);}CProgrammingLanguage24折半查找程序#includestdio.hmain(){intup=9,low=0,mid,found=0,find;inta[10]={1,5,6,9,11,17,25,34,38,41};scanf(〞%d〞,&find);printf(〞\n〞);while(up=low&&!found){mid=(up+low)/2;if(a[mid]==find){found=1;break;}elseif(a[mid]find)up=mid-1;elselow=mid+1;}if(found)printf(〞foundnumberis%dth〞mid);elseprintf(〞nofound〞);}CProgrammingLanguage25补充知识二：数组元素的插入、删除1、插入数据•在有序数组中插入数据后，数组仍然有序。•要求数组有足够的空间。前提：被操作数组已经是有序数组，操作前后不改变数组的有序性CProgrammingLanguage26插入过程：(1)确定数据插入位置(2)从最后一个元素开始逐个后移，直到将第i个位置腾出。(a[i+1]=a[i])(3)将数据插入到指定下标元素位置中CProgrammingLanguage27插入运算ai-1…..a1a0alength…ai+1aixai-1…..a1a0aiai+1…alengthalength……ai+1aix…CProgrammingLanguage282、删除数据在有序的数组中删除数据后，数组仍然有序。删除过程：(1)确定数据删除位置i(2)从第i＋1个位置开始逐个向前移动原数组元素，(a[i]=a[i+1])CProgrammingLanguage29下面介绍引用一维数组元素的三种方式。1.下标方式形式：数组名[下标],如a[i]2.地址方式形式：*（地址）,如*(a+i)等价a[i]3.指针方式形式：*指针变量名如:inta[10],*p；p=&a[i],*p=a[i];CProgrammingLanguage30一维数组与指针1数组就是连续存放的若干元素的集合。2数组名就是指向数组第一个元素的首地址（指针）如inta[10],*p；则p=a等价于p=&a[0]；3某一元素的地址：p=&a[i]，则用指针引用该元素为：*p=a[i];4数组元素下标在内部实现时，统一按“基地址＋位移”的方式处理。即：a，a＋1，a＋i；表示数组的地址可用：p+i，a+i表示数组的内容可用：a[i]，*(p+i)，*(a+i)注意：虽然a与p都可以指示地址，但a是指首地址，p