常见三种排序方法-课件.ppt

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 进

2、行进行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?(递增递增)q(1)从从n个数的序列中选出最小的数，与第个数的序列中选出最小

3、的数，与第1个数交个数交换位置；换位置；q(2)除第除第1个数外，其余个数外，其余n-1个数再按个数再按(1)的方法选出的方法选出次小的数，与第次小的数，与第2个数交换位置个数交换位置;q(3)重复重复(1)n-1遍，最后构成递增序列。遍，最后构成递增序列。p外循环为外循环为：控制排序趟数：控制排序趟数p内循环为内循环为：第：第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不在本次排序中的位置（由小到大排序）4936416511783665364156

4、364165413641561178363641491156492525251149495611111125252525交交 换换 排排 序序“冒泡冒泡”排序法排序法特点：逐个对数组中每相邻二数进行比较，若条件满特点：逐个对数组中每相邻二数进行比较，若条件满 足，则互相交换，否则保持原位置不变。足，则互相交换，否则保持原位置不变。若有若有n个数据，需要进行个数据，需要进行i=n-1轮比较轮比较。每轮中比较。每轮中比较的次数为的次数为j=n-i+1 次。次。排序过程：（设数据存于排序过程：（设数据存于A数组中，数组中，n个数据，按递增个数据，按递增 次序排序）次序排序）冒泡法排序for(i=1;

5、i n;i+);jaj+1)t=aj;aj=aj+1;aj+1=t;关键代码：for(i=0 ;i n-1 ;i+)for(j=0 ;jaj+1)t=aj;aj=aj+1;aj+1=t;注意排序堂数注意排序堂数i的初值的初值注意注意i的边界的边界注意注意j的边界的边界冒泡程序（上机19、52套编程题）for(i=0 ;i n-1 ;i+)for(j=i+1 ;jaj)t=ai;ai=aj;aj=t;注意排序堂数i的初值注意i的边界注意j的边界注意ai与aj比较补充知识一：查找补充知识一：查找查找的方法很多。查找的方法很多。如：顺序查找、二分法查找等等。如：顺序查找、二分法查找等等。1、顺序查找

6、：、顺序查找：最简单的查找方法，基本思想是利用循最简单的查找方法，基本思想是利用循环顺序扫描整个数组，依次将每个元素环顺序扫描整个数组，依次将每个元素与待查找值比较，直至找到或找不到。与待查找值比较，直至找到或找不到。对于无序数组，顺序查找是唯一可行的办法对于无序数组，顺序查找是唯一可行的办法 对大批量数据用顺序查找占机器时间较多。对大批量数据用顺序查找占机器时间较多。2、二分法查找、二分法查找/折半查找：折半查找：二分法查找的条件：二分法查找的条件：必须是有序数列，即数组中的各必须是有序数列，即数组中的各元素已按数值大小按递增或递减元素已按数值大小按递增或递减次序排列！次序排列！查找过程：查

7、找过程：(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

8、,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=(u

9、p+low)/2=1 up=3 low=2 mid=(up+low)/2=2 up=3 low=3 mid=(up+low)/2=3折半查找程序#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(fo

10、und 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)