常见三种排序方法.ppt

数组操作数组操作n n（1）选择排序法选择排序法n n（2）冒泡排序）冒泡排序法法n n（3）比较排序法）比较排序法n n（1）顺序查找法）顺序查找法n n（2）折半查找法）折半查找法n n（1）数组元素插入）数组元素插入n n（2）数组元素删除）数组元素删除（1 1）选择排序第17、26套的填空题简单选择排序简单选择排序:从从1到到n 选选出出关关键键值值最最（大大）小小的的记记录录，交交换换到到第第一一个个位位置置上上，然然后后从从2到到n选选 出出键键值值最最（大大）小小的的记记录录，交交换换到到第第 二个位置上，二个位置上，.54 71 58 29 3154 71 58 29 3154 71 58 29 3154 71 58 29 31i=0初态初态k=0数组下标数组下标 0 1 2 3 4j=1k=0j=2k=0j=3k=3j=4k!=i,交换交换第第一一趟趟互换互换i=0判断判断ajak?用选择法对数组用选择法对数组 int a5=54,71,58,29,31 进行进行升序排序升序排序升序排序升序排序k=jk=1j=2i=1 29 71 58 54 31j=3k=2i=1第第二二趟趟 29 71 58 54 3129 71 58 54 31i=1k=3 j=429 71 58 54 31i=1k=4k!=i,交换交换互换互换29 31 58 54 71判断判断ajak?k=jk=jk=j29 31 58 54 71i=2k=2j=329 31 58 54 71i=2k=3j=429 31 54 58 71互换互换第第三三趟趟k!=i,交换交换i=3k=3j=4k=i,不交换不交换第第四四趟趟判断判断ajak?“选择排序法选择排序法”（由小到大排序）（由小到大排序）n n选择法选择法(递增递增)n n基本思想：基本思想：q(1)从从n个数的序列中选出最小的数，与第个数的序列中选出最小的数，与第1个数交个数交换位置；换位置；q(2)除第除第1个数外，其余个数外，其余n-1个数再按个数再按(1)的方法选出的方法选出次小的数，与第次小的数，与第2个数交换位置个数交换位置;q(3)重复重复(1)n-1遍，最后构成递增序列。遍，最后构成递增序列。n n实现方法：采用双重循环（循环的嵌套）实现方法：采用双重循环（循环的嵌套）p外循环为外循环为i i：控制排序趟数：控制排序趟数p内循环为内循环为j 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;#include#include#include stdlib.h#include stdlib.hvoid main()void main()const int N=10;const int N=10;int i,j,k,t,aN;int i,j,k,t,aN;for(i=0;i N;i+)for(i=0;i N;i+)ai=rand()%61;ai=rand()%61;printf(%d,ai);printf(%d,ai);printf(n);printf(n);for(i=0;i N-1;i+)for(i=0;i N-1;i+)k=i;k=i;for(j=i+1;j aj)k=j;for(j=i+1;j aj)k=j;if(k!=i)t=ak;ak=ai;ai=t;if(k!=i)t=ak;ak=ai;ai=t;for(i=0;iN;i+)printf(%5d,ai);for(i=0;iN;i+)printf(%5d,ai);printf(n);printf(n);第二种：“冒泡法”（由小到大排序）n n基本思想：基本思想：qq(1)(1)从第一个元素开始，对数组中两两相邻的元素从第一个元素开始，对数组中两两相邻的元素从第一个元素开始，对数组中两两相邻的元素从第一个元素开始，对数组中两两相邻的元素比较，将值较小的元素放在前面，值较大的元素比较，将值较小的元素放在前面，值较大的元素比较，将值较小的元素放在前面，值较大的元素比较，将值较小的元素放在前面，值较大的元素放在后面，一轮比较完毕，最大的数存放在放在后面，一轮比较完毕，最大的数存放在放在后面，一轮比较完毕，最大的数存放在放在后面，一轮比较完毕，最大的数存放在aN-aN-11中；中；中；中；qq (2)(2)然后对然后对然后对然后对a0a0到到到到aN-2aN-2的的的的N-1N-1个数进行同（个数进行同（个数进行同（个数进行同（1 1）的）的）的）的操作，次最大数放入操作，次最大数放入操作，次最大数放入操作，次最大数放入aN-2aN-2元素内，完成第二趟排元素内，完成第二趟排元素内，完成第二趟排元素内，完成第二趟排序；依次类推，进行序；依次类推，进行序；依次类推，进行序；依次类推，进行N-1N-1趟排序后，所有数均有序。趟排序后，所有数均有序。趟排序后，所有数均有序。趟排序后，所有数均有序。n n实现方法：采用双重循环（循环的嵌套）实现方法：采用双重循环（循环的嵌套）4936416511第第第第六六六六趟趟趟趟排排排排序序序序后后后后第第第第五五五五趟趟趟趟排排排排序序序序后后后后第第第第四四四四趟趟趟趟排排排排序序序序后后后后第第第第三三三三趟趟趟趟排排排排序序序序后后后后第第第第二二二二趟趟趟趟排排排排序序序序后后后后第第第第一一一一趟趟趟趟排排排排序序序序后后后后初初初初始始始始关关关关键键键键字字字字783665364156364165413641561178363641491156492525251149495611111125252525（2 2 2 2）冒泡排序）冒泡排序）冒泡排序）冒泡排序 交换排序：俩俩比较待排序记录的键值，若逆序，则交换，交换排序：俩俩比较待排序记录的键值，若逆序，则交换，交换排序：俩俩比较待排序记录的键值，若逆序，则交换，交换排序：俩俩比较待排序记录的键值，若逆序，则交换，直到全部满足为止直到全部满足为止直到全部满足为止直到全部满足为止交交 换换 排排 序序“冒泡冒泡”排序法排序法特特点点：逐逐个个对对数数组组中中每每相相邻邻二二数数进进行行比比较较，若若条条件件满满 足，则互相交换，否则保持原位置不变。足，则互相交换，否则保持原位置不变。千万要注意！千万要注意！千万要注意！千万要注意！若若有有n个个数数据据，需需要要进进行行i=n-1轮轮比比较较。每每轮轮中中比比较较的次数为的次数为j=n-i+1 次。次。排序过程：（设数据存于排序过程：（设数据存于A数组中，数组中，n个数据，按递增个数据，按递增 次序排序）次序排序）A0A0与与与与A1A1比较比较比较比较 A0A(1)A0A(1)不换，否则对调不换，否则对调不换，否则对调不换，否则对调A1A1与与与与A2A2比较比较比较比较 A1A2 A1A2 不换，否则对调不换，否则对调不换，否则对调不换，否则对调 ：An-2An-2与与与与An-1An-1比较比较比较比较 An-2An-1 An-2An-1 不换，否则对调不换，否则对调不换，否则对调不换，否则对调冒泡法排序用冒泡法对用冒泡法对10个数排序个数排序(由小到大由小到大)。482759248579245879245789245789245789冒泡排序的结构形式（递增）冒泡排序的结构形式（递增）for(i=0;iN-1;i+)for(i=0;iN-1;i+)for(j=0;jN-i-1;j+)for(j=0;jaj+1)t=aj;aj=aj+1;aj+1=t;if(ajaj+1)t=aj;aj=aj+1;aj+1=t;for(i=1;i n;i+)for(j=0 ;jaj+1)t=aj;aj=aj+1;aj+1=t;关键代码：1414for(i=0 ;i n-1 ;i+)for(j=0 ;jaj+1)t=aj;aj=aj+1;aj+1=t;#include#include#define N 6#define N 6void main()void main()int i,j,t,aN;int i,j,t,aN;printf(input N numbers:n);printf(input N numbers:n);for(i=0;iN;i+)for(i=0;iN;i+)scanf(%d,&ai);scanf(%d,&ai);printf(n);printf(n);for(i=0;iN-1;i+)for(i=0;iN-1;i+)for(j=0;jN-i-1;j+)for(j=0;jaj+1)t=aj;aj=aj+1;aj+1=t;if(ajaj+1)t=aj;aj=aj+1;aj+1=t;for(i=0;iN;i+)printf(%5d,ai);for(i=0;iN;i+)printf(%5d,ai);printf(n);printf(n);冒泡程序第三种：比较排序（上机19、52套编程题）for(i=0 ;i n-1 ;i+)for(j=i+1 ;jaj)t=ai;ai=aj;aj=t;注意ai与aj比较补充知识一：查找补充知识一：查找查找的方法很多。查找的方法很多。如：顺序查找、二分法查找等等。如：顺序查找、二分法查找等等。1、顺序查找：、顺序查找：最最简简单单的的查查找找方方法法，基基本本思思想想是是利利用用循循环环顺顺序序扫扫描描整整个个数数组组，依依次次将将每每个个元元素素与待查找值比较，直至找到或找不到。与待查找值比较，直至找到或找不到。对于无序数组，顺序查找是唯一可行的办法对于无序数组，顺序查找是唯一可行的办法对大批量数据用顺序查找占机器时间较多。对大批量数据用顺序查找占机器时间较多。int Search(long a,int n,long x)int Search(long a,int n,long x)int i;int i;for(i=0;in;i+)for(i=0;in;i+)if(ai=x)if(ai=x)return(i);return(i);return(-1);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)lowmid(08,14,23,37,46,55,68,79,91)lowmidmidlowmidmidlowhigh=mid-1highhighhigh 折半查找（二分法查找）折半查找（二分法查找）highlow(08,14,23,37,46,55,68,79,91)midlowhigh 下标下标 0 1 2 3 4 5 6 7 8 折半查找1，5，6，9，11，17，25，34，38，41下界下界lowlow上界上界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=3int BinSearch(long a,int n,long x)int BinSearch(long a,int n,long x)int low,high,mid;int low,high,mid;low=0;low=0;high=n-1;high=n-1;while(low=high)while(low amid)if(x amid)low=mid+1;low=mid+1;else if(x amid)high=mid-1;else if(x amid)high=mid-1;else return(mid);else return(mid);return(-1);return(-1);折半查找程序#include main()int up=9,low=0,mid,found=0,find;int a10=1,5,6,9,11,17,25,34,38,41;scanf(%d,&find);printf(n);while(up=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)将数据插入到指定下标元素位置中将数据插入到指定下标元素位置中 插入运算插入运算ai-1.a1a0alength ai+1ai x ai-1.a1 a0 ai ai+1 alength alength ai+1 ai x 2、删除数据、删除数据在有序的数组中删除数据后，数组仍然有序。在有序的数组中删除数据后，数组仍然有序。删除过程：删除过程：(1)确定数据删除位置确定数据删除位置i(2)从从第第i1个个位位置置开开始始逐逐个个向向前前移移动动原原数数组组元元素素，(ai=ai+1)下面介绍引用一维数组元素的三种方式。下面介绍引用一维数组元素的三种方式。下面介绍引用一维数组元素的三种方式。下面介绍引用一维数组元素的三种方式。1.1.1.1.下标方式下标方式下标方式下标方式形式：形式：形式：形式：数组名数组名数组名数组名 下标下标下标下标 ,如如如如aiai 2.2.2.2.地址方式地址方式地址方式地址方式 形式：形式：形式：形式：*（地址）（地址）（地址）（地址）,如如如如*(a+i)(a+i)等价等价等价等价aiai 3.3.3.3.指针方式指针方式指针方式指针方式 形式：形式：形式：形式：*指针变量名指针变量名指针变量名指针变量名 如如如如:int a10,*pint a10,*p；p=&aip=&ai,*p=ai;*p=ai;一维数组与指针一维数组与指针n n1 1数组就是连续存放的若干元素的集合。数组就是连续存放的若干元素的集合。数组就是连续存放的若干元素的集合。数组就是连续存放的若干元素的集合。n n2 2数组名就是指向数组第一个元素的首地址（指针）数组名就是指向数组第一个元素的首地址（指针）数组名就是指向数组第一个元素的首地址（指针）数组名就是指向数组第一个元素的首地址（指针）如如如如 int a10,*pint a10,*p；则；则；则；则p=ap=a等价于等价于等价于等价于p=&a0p=&a0；n n3 3某一元素的地址：某一元素的地址：某一元素的地址：某一元素的地址：p=&aip=&ai，则用指针引用该元素为：，则用指针引用该元素为：，则用指针引用该元素为：，则用指针引用该元素为：*p=ai;p=ai;n n4 4数组元素下标在内部实现时，统一按数组元素下标在内部实现时，统一按数组元素下标在内部实现时，统一按数组元素下标在内部实现时，统一按“基地址位移基地址位移基地址位移基地址位移”的方式处理。即：的方式处理。即：的方式处理。即：的方式处理。即：a a，a a1 1，a ai i；uu表示数组的地址可用：表示数组的地址可用：表示数组的地址可用：表示数组的地址可用：p+ip+i，a+ia+iuu表示数组的内容可用：表示数组的内容可用：表示数组的内容可用：表示数组的内容可用：ai ai，*(p+i)(p+i)，*(a+i)(a+i)注意：虽然注意：虽然注意：虽然注意：虽然a a与与与与p p都可以指示地址，但都可以指示地址，但都可以指示地址，但都可以指示地址，但a a是指首地址，是指首地址，是指首地址，是指首地址，p p是变是变是变是变量（可以指首地址，也可以指其他地址）量（可以指首地址，也可以指其他地址）量（可以指首地址，也可以指其他地址）量（可以指首地址，也可以指其他地址）