C+程序设计程序设计第第6章章(2)顺序表的排序和查找顺序表的排序和查找1主要内容主要内容l查找与排序查找与排序l常用查找方法常用查找方法顺序查找顺序查找l常用查找方法常用查找方法折半查找（二分法查找）折半查找（二分法查找）l插入排序法插入排序法直接插入、折半插入直接插入、折半插入l选择排序法选择排序法l冒泡冒泡排序法排序法l索引排序与查找索引排序与查找2查找与排序查找与排序l查找：查找：指在一组数据元素中寻找满足条件的数据元素，并进一步给出其具体信息。指在一组数据元素中寻找满足条件的数据元素，并进一步给出其具体信息。l常用查找方法：常用查找方法：顺序查找顺序查找 折半查找折半查找l排序：排序：指指将一组数据元素从无序序列调整为有序序列。从小到大的排序称为升序，将一组数据元素从无序序列调整为有序序列。从小到大的排序称为升序，从大到小的排序称为降序。从大到小的排序称为降序。关键字：关键字：若若待排序的待排序的数据元素含有多个成员数据项，可根据排序需要选择其中的一个数据元素含有多个成员数据项，可根据排序需要选择其中的一个成员数据项作为依据进行排序，称以该成员数据项为关键字的排序。也可选择其中成员数据项作为依据进行排序，称以该成员数据项为关键字的排序。也可选择其中的若干个关键字为依据进行排序，先按主关键字进行排序，而主关键字相同的数据的若干个关键字为依据进行排序，先按主关键字进行排序，而主关键字相同的数据元素之间，再按次关键字进行排序元素之间，再按次关键字进行排序 。稳定排序：稳定排序：指指当当两个数据元素两个数据元素关键字相同时，原来排在前的仍然排在前。关键字相同时，原来排在前的仍然排在前。l常用排序方法：常用排序方法：插入排序插入排序 选择排序选择排序 冒泡排序冒泡排序3常用查找方法常用查找方法顺序查找顺序查找l顺序查找方法：顺序查找方法：指指从第一个数据元素开始，依次顺序查找下去，直到找到要找的元从第一个数据元素开始，依次顺序查找下去，直到找到要找的元素为止，或者一直找到最后一个元素也未找到。素为止，或者一直找到最后一个元素也未找到。l顺序查找函数模板：顺序查找函数模板：（保存在（保存在头文件头文件“search.h”中）中）template int sequentSearch(T sL ,int n,T k )/在数组在数组 sL n 中查找数据中查找数据 k for(int i=0;in;i+)if(sL i =k )return i;/找到时，返回所找到元素的下标找到时，返回所找到元素的下标 return -1;/找不到时，返回找不到时，返回-1 4addr endl;if(k!=i )temp=sL i ;sL i =sL k ;sL k =temp;for(i=0;i8;i+)cout ps i endl;直接插入排序函数模板（升序）：（保存在头文件“sort.mid=(low+high)/2;cout“排序后通过索引学生资料为：n”;#include“search.void main()折半查找（递归算法）函数模板：（保存在头文件“search.if(k sL mid )mid=binarySearch2(sL,low,mid-1,k);/递归调用16 37 41 56 69 74 78 88 92 99void main()cout setw(6)score;char *ps 8 =“You are student!”,“Beijing,China”,选择排序的基本思想（升序）：每一趟从待排序的元素中选出最小的元素，顺序放在已排好序的子序列的后面，直到全部元素都被选出并排好序。插入排序法直接插入【例】（对函数【例】（对函数 sequentSearch()进行测试。进行测试。）#include#include#include“search.h”void main()int a 10 ,k;cout “数组中的数据为：数组中的数据为：n”;for (int i=0;i10;i+)a i =rand()%90+10;cout a i “”;cout endl;cout k;i=sequentSearch (a,10,k );if (i!=-1)cout a i “已找到，下标已找到，下标=”i endl;else cout k “未找到未找到!n”;第一次运行：第一次运行：数组中的数据为：数组中的数据为：51 27 44 50 99 74 58 28 62 84请输入要查找的数：请输入要查找的数：66 66未找到未找到！第二次运行：第二次运行：数组中的数据为：数组中的数据为：51 27 44 50 99 74 58 28 62 84请输入要查找的数：请输入要查找的数：99 99已找到，下标已找到，下标=45常用查找方法常用查找方法折半查找（二分法查找）折半查找（二分法查找）l折半查找的前提条件：折半查找的前提条件：数组必须有序，才能使用折半查找。数组必须有序，才能使用折半查找。l折半查找方法：折半查找方法：（假设数组元素已升序排列）（假设数组元素已升序排列）设置查找区间：设置查找区间：定义两个指针定义两个指针low、high分别指向数组的首、尾两个元素；分别指向数组的首、尾两个元素；折半取区间中点：折半取区间中点：若查找区间存在，即若查找区间存在，即low mid所指的元素，所指的元素，则：取则：取 low=mid+1，high不变，继续查找，重复不变，继续查找，重复；w若所要找的元素若所要找的元素 high 仍未查找到，则：表示找不到，查找失败，停止！仍未查找到，则：表示找不到，查找失败，停止！674 78 88 92 99high=9mid=(5+9)/2=7low=4+1=5 16 37 41 56 69 74 78 88 92 99mid=(0+9)/2=4high=9low=00 1 2 3 4 5 6 7 8 988（查找成功例）（查找成功例）16 37 41 56 69 74 78 88 92 99mid=(0+9)/2=4high=9low=00 1 2 3 4 5 6 7 8 916 37 41 56mid=(0+3)/2=1high=4-1=3 low=041 56low=1+1=2 high=3 mid=(2+3)/2=256 high=3low=3 mid=(3+3)/2=367（查找失败例）（查找失败例）7常用查找方法常用查找方法折半查找（二分法查找）折半查找（二分法查找）l折半查找（折半查找（迭代算法）迭代算法）函数模板：函数模板：（保存在（保存在头文件头文件“search.h”中）中）template int binarySearch1 (T sL ,int n,T k )/在数组在数组 sL n 中查找数据中查找数据 k int low=0,high=n-1,mid;while(low=high )mid =(low+high)/2;if (k=sL mid )return mid;/找到时，返回所找到元素的下标找到时，返回所找到元素的下标 if (k sL mid )high=mid-1;/左缩查找区间左缩查找区间 else low=mid+1;/右缩查找区间右缩查找区间 return-1;/找不到时，返回找不到时，返回-18常用查找方法常用查找方法折半查找（二分法查找）折半查找（二分法查找）l折半查找（折半查找（递归算法）递归算法）函数模板：函数模板：（保存在（保存在头文件头文件“search.h”中）中）template /在数组在数组 sL n 中下标中下标区间区间 low high 之间查找数据之间查找数据 kint binarySearch2 (T sL ,int low,int high,T k )int mid=-1;/找不到时，返回找不到时，返回-1 if (low sL mid )mid=binarySearch2(sL,mid+1,high,k);/递归调递归调用用 if(k sL mid )mid=binarySearch2(sL,low,mid-1,k);/递归调递归调用用 return mid;9【例】（对函数【例】（对函数 binarySearch1()、binarySearch2()进行进行测试。测试。）#include#include“search.h”void main()int a 6 =32,45,56,78,88,97 ,k;cout “数组中的数据为：数组中的数据为：”;for(int i=0;i6;i+)cout a i “”;cout endl;cout k;i=binarySearch1 (a,6,k);if (i!=-1)cout a i “已找到，下标已找到，下标=”i endl;else cout k “未找到未找到!n”;i=binarySearch2 (a,0,5,k);if (i!=-1)cout a i “已找到，下标已找到，下标=”i endl;else cout k “未找到未找到!n”;第一次运行：第一次运行：数组中的数据为：数组中的数据为：32 45 56 78 88 97请输入要查找的数据：请输入要查找的数据：57 57未找到！未找到！57未找到！未找到！第二次运行：第二次运行：数组中的数据为：数组中的数据为：32 45 56 78 88 97请输入要查找的数据：请输入要查找的数据：78 78已找到，下标已找到，下标=378已找到，下标已找到，下标=310插入排序法插入排序法直接插入、折半插入直接插入、折半插入l插入排序的基本思想插入排序的基本思想：每一趟依次将待排序元素中的首个元素每一趟依次将待排序元素中的首个元素有序地插入有序地插入到到其前面其前面已排好序的子序列已排好序的子序列中，直到全部元素都被插入并排好序。中，直到全部元素都被插入并排好序。l直接插入排序直接插入排序：当插入第当插入第 i 个元素时，其前面的第个元素时，其前面的第 0 i-1 个元素子序列已排好序，个元素子序列已排好序，只需将要插入的元素与其前面子序列中的元素只需将要插入的元素与其前面子序列中的元素从后向前依次顺序比较从后向前依次顺序比较，找到插入点，找到插入点并将其插入。并将其插入。l折半插入排序折半插入排序：就是在寻找插入点的时候，就是在寻找插入点的时候，用折半查找取代顺序查找用折半查找取代顺序查找。折半插入优。折半插入优于直接插入，它利用了数据元素排列中的部分有序性。于直接插入，它利用了数据元素排列中的部分有序性。11插入排序法插入排序法直接插入直接插入l直接插入排序过程（升序）直接插入排序过程（升序）：设数组为：设数组为：a0 a1 a6 a7；第第1趟插入：趟插入：初始时已排好序的子序列为：初始时已排好序的子序列为：a0；要插入的元素是：；要插入的元素是：a1；将将a1与与a0比较，若比较，若a0小，则将小，则将a1插入在其后，否则反之。插入在其后，否则反之。第第1趟后，子序列趟后，子序列 a0 a1 已排好序，待排序的元素减缩为：已排好序，待排序的元素减缩为：a2 a7；第第2趟插入：趟插入：已排好序的子序列为：已排好序的子序列为：a0 a1；要插入的元素是：；要插入的元素是：a2；将将a2依次与依次与a1、a0比较，找到第一个比比较，找到第一个比a2小的，则小的，则a2插入在其后。插入在其后。第第2趟后，子序列趟后，子序列 a0 a1 a2 已排好序，待排序的元素减缩为：已排好序，待排序的元素减缩为：a3 a7；经过经过7趟插入后：趟插入后：a0 a1 a6 a7 全部排好序。全部排好序。12mid=(0+9)/2=4直接插入排序函数模板（升序）：（保存在头文件“sort.【例】（对直接插入排序函数 insertSort()进行测试。数组中的数据为：32 45 56 78 88 97mid=(2+3)/2=2if (k=sL mid )return mid;/找到时，返回所找到元素的下标cout “排序前：”