第18部分 排序与搜索初步

1,第十八章 排序与搜索初步,2,本章主要内容,排序含义与目的基本排序方法插入、选择和冒泡排序查找与搜索基本知识简单查找方法顺序查找与折半查找搜索方法深度优先搜索广度优先搜索,3,一、排序,把一组数据的排列顺序按照某种标准重新排列。例如对数值型数据，可能希望把它们按照从小到大的顺序重排。这种操作称为排序,4,最基本的排序方法,直接插入排序法选择排序法冒泡排序,5,1. 直接插入排序法,直接插入排序法例如，假定有一年的杂志，现在想把它们从1月到12月排好。插入排序方法是：1. 任取一本杂志，作为排好序的一叠杂志的开始情况2. 从剩余杂志中任取一本，根据月份把它插入排好序的那叠杂志里的正确位置，使插入后的这叠杂志仍有序3.如果还有未排好的杂志，就回到2，否则就结束,6,排序过程,假定有n项数据存放在数组里，现希望把它们按从小到大的顺序重新排列。考虑排序中的状态，左边积累排好序的元素，右边是尚未排序的元素。一般状态的情况：,下标0到i-1的部分已排序。反复把i处的数据插入已排序部分。随着i增大右段越来越短，最终所有数据都排好。开始令左段只有一个元素（单元素序列总已排序），,7,过程描述,for (i = 1; i n; +i) 把ai的值插入a0到ai-1一段里的正确位置，保持其他元素顺序不变假定有n项数据存放在数组里，现希望把它们按从小到大的顺序重新排列。,8,排序过程中的数据插入,考虑元素ai的插入。把ai存入临时变量t里，下标i的位置闲置。用t逐个与ai-1到a0比较，一旦遇到某个元素不比t大（前面已经比过的元素都大于t），就把t排在它的后面。由于ai是空位，比较时把大元素依次后移，当遇到不大于t的元素时，正好把t放入空位，a里的前i个值就排好序了。过程中的情况,9,直接插入排序法示例,i=1,i=2,i=3,i=4,i=5,i=6,i=9,10,排序函数的定义,void insertsort(int nLen, int narr) /* 递增序直接插入排序 */ int i, j; int t; for( i = 1; i = 0 ,11,2. 选择排序方法,选择排序法思想从未排序数据中选出最小元素，与第一个元素交换位置再从剩下的数据中找出次小的元素，与第二个元素交换位置依此类推，直到数组有序为止。,12,start,min,min,start,min,start,min,start,start,min,start,min,start,min,13,int SelectiveSort(int narr, int nLen)int nStartPos, nCurPos, nMinPos, nTemp;/nStartPos:无序元素起点，nCurPos:选择过程中的当前元素，/nMinPos:当前轮次最小元素所在位置，nTemp:临时变量if (NULL = narr) | (nLen 0) return -1;/合法性检查for (nStartPos = 0; nStartPos nLen - 1; nStartPos+)/开始排序nMinPos = nStartPos;for (nCurPos = nStartPos + 1; nCurPos nLen - 1; nCurPos+)if (narrnCurPos narrnMinPos)nMinPos = nCurPos;if (nMinPos != nStartPos) /交换位置nTemp = narrnStartPos;narrnStartPos = narrnMinPos;narrnMinPos = nTemp;return 0;,14,3. 冒泡排序法思想,进行若干轮排序，在每轮排序中，将两邻两个数进行比较，根据大小顺序交换元素位置。如非递减排序时，将小的换到前面，大的换到后面。这样通过一轮的排序，使小的数往上冒一层，大数往下沉了若干层。若某一轮没有发生交换，则说明已经有有序，排序结果。,15,冒泡排序法,685974,685974,658974,658974,658794,658749,568749,568749,567849,567489,567489,567489,564789,564789,546789,456789,第1轮,第2轮,第3轮,第4轮,第5轮,红色数字表示每次将进行的比较两邻元素根据前后的大小关系决定是否进行位置交换,16,int BubbleSort(int narr, int nLen)int i, j; /循环量int nTemp; /temp variable for exchangingif (nLen narrj + 1) /如果前面的元素大于后面的元素 / exchange two elements nTemp = narrj; narrj = narrj + 1; narrj + 1 = nTemp; return 0;,17,二、查找,查找在一个数据集合中查找一个符合给定条件的子集合关键：功能 vs 效率,18,简单的查找功能示例,数组查找示例在无序数组中找出数组中的最大元素所在位置，并返回。有无序数组中找出数组中的最小元素所在位置，并返回。给定某个值，在无序数组中找出该元素在数组中的第一次出现的位置，并返回。给定某个值，在有序数组中用折半查找法查找某个元素在数组中的位置返回。,19,复杂的查找功能示例,在大规模的数据集合中快速的寻找到符合给定条件的数据搜索服务商在其分布式存放的大规模的网页数据中找到与关键字集匹配的网页，并按相关性或网页主人的出价等因素给搜索结果排序分页列出。在大规模的网络图片或视频流中找出符合关键字或某些特征要求的图片棋类游戏在可行的下法中搜索一个相对合理的下法。斗地主游戏程序的托管功能：托管时根据当前出牌牌型，在被托管游戏者的手中的牌中自动寻找一套符合牌型要求的最小的并能大过上家的出牌的出法。找到就出出去，找不到PASS。,20,查找程序示例,在无序数组中找出数组中的最大元素所在位置，并返回。待续,21,折半查找法,在有序数据中查找给定数据的一种有效方法思想给定需要查找的值，给定查找范围。将给定值与查找范围的中间位置元素进行比较。如果找到则结束，否则根据比较结果将查找范围缩小一半。,22,示意图,Left = 0,Right = 14,Mid = 7,查找 70,Left = 8,Right = 14,Mid = 11,23,int BiSearch(int narr, int nLen, int nValue)int nMid, /当前位置 nLeft = 0,/查找范围的左边界 nRight = nLen - 1; /查找范围的右边界if (narr = NULL | nLen nValue) /如果中间位置的值大于查找值，则在左侧区间中找 nRight = nMid -1; /修改右边界 else return nMid;/找到该元素，返回该元素所在位置return -1; /没找到,24,三、搜索初步,是根据问题的性质，找出问题的状态模型，确