常见三种排序方法.ppt

数组操作,（1）选择排序法（2）冒泡排序法（3）比较排序法,（1）顺序查找法（2）折半查找法,（1）数组元素插入（2）数组元素删除,（1）选择排序第17、26套的填空题,简单选择排序:从1到n选出关键值最（大）小的记录，交换到第一个位置上，然后从2到n选出键值最（大）小的记录，交换到第二个位置上，.,5471582931547158293154715829315471582931,i=0,初态,数组下标01234,k!=i,交换,判断ajak?,用选择法对数组inta5=54,71,58,29,31进行升序排序,k=j,2971585431,2971585431,2971585431,2971585431,k!=i,交换,2931585471,判断ajak?,k=j,k=j,k=j,判断ajak?,“选择排序法”（由小到大排序）选择法(递增)基本思想：(1)从n个数的序列中选出最小的数，与第1个数交换位置；(2)除第1个数外，其余n-1个数再按(1)的方法选出次小的数，与第2个数交换位置;(3)重复(1)n-1遍，最后构成递增序列。实现方法：采用双重循环（循环的嵌套）外循环为i：控制排序趟数内循环为j：第i趟排序过程中的下标变量,“选择”排序法的结构形式：,for(i=0;iaj)k=j;if(k!=i)t=ai;ai=ak;ak=t;,#include#includestdlib.hvoidmain()constintN=10;inti,j,k,t,aN;for(i=0;iaj)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趟排序后，所有数均有序。实现方法：采用双重循环（循环的嵌套）,（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个数排序(由小到大)。,482759,248579,245879,245789,245789,245789,冒泡排序的结构形式（递增）,for(i=0;iaj+1)t=aj;aj=aj+1;aj+1=t;,for(i=1;iaj+1)t=aj;aj=aj+1;aj+1=t;,关键代码：,14,for(i=0;iaj+1)t=aj;aj=aj+1;aj+1=t;,#include#defineN6voidmain()inti,j,t,aN;printf(inputNnumbers:n);for(i=0;iaj+1)t=aj;aj=aj+1;aj+1=t;for(i=0;iN;i+)printf(%5d,ai);printf(n);,冒泡程序,第三种：比较排序（上机19、52套编程题）,for(i=0;iaj)t=ai;ai=aj;aj=t;,注意ai与aj比较,补充知识一：查找,查找的方法很多。如：顺序查找、二分法查找等等。,1、顺序查找：最简单的查找方法，基本思想是利用循环顺序扫描整个数组，依次将每个元素与待查找值比较，直至找到或找不到。,对于无序数组，顺序查找是唯一可行的办法对大批量数据用顺序查找占机器时间较多。,intSearch(longa,intn,longx)inti;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),(08,14,23,37,46,55,68,79,91),折半查找（二分法查找）,(08,14,23,37,46,55,68,79,91),下标012345678,折半查找,1，5，6，9，11，17，25，34，38，41,下界low,上界up,中值mid,共有10个已排好序的数据：查找9。,intBinSearch(longa,intn,longx)intlow,high,mid;low=0;high=n-1;while(lowamid)low=mid+1;elseif(xamid)high=mid-1;elsereturn(mid);return(-1);,折半查找程序,#includemain()intup=9,low=0,mid,found=0,find;inta10=1,5,6,9,11,17,25,34,38,41;scanf(%d,补充知识二：数组元素的插入、删除,1、插入数据在有序数组中插入数据后，数组仍然有序。要求数组有足够的空间。,前提：被操作数组已经是有序数组，操作前后不改变数组的有序性,插入过程：(1)确定数据插入位置(2)从最后一个元素开始逐个后移，直到将第i个位置腾出。(ai+1=ai)(3)将数据插入到指定下标元素位置中,插入运算,ai-1,.,a1,a0,alength,ai+1,ai,x,x,2、删除数据在有序的数组中删除数据后，数组仍然有序。,删除过程：(1)确定数据删除位置i(2)从第i1个位置开始逐个向前移动原数组元素，(ai=ai+1),下面介绍引用一维数组元素的三种方式。1.下标方式形式：数组名下标,如ai2.地址方式形式：*（地址）,如*(a+i)等价ai3.指针方式形式：*指针变量名如:inta10,*p；p=,一维数组与指针,1数组就是连续存放的若干元素的集合。2数组名就是指向数组第一个元素的首地址（指针）如i