第-章━━顺序表的排序和查找

C++程序设计第6章(2)

━━顺序表的排序和查找1主要内容查找与排序常用查找方法━━顺序查找常用查找方法━━折半查找（二分法查找）插入排序法━━直接插入、折半插入选择排序法冒泡排序法索引排序与查找2查找与排序查找：指在一组数据元素中寻找满足条件的数据元素，并进一步给出其具体信息。常用查找方法：①顺序查找

②折半查找排序：指将一组数据元素从无序序列调整为有序序列。从小到大的排序称为升序，从大到小的排序称为降序。①关键字：若待排序的数据元素含有多个成员数据项，可根据排序需要选择其中的一个成员数据项作为依据进行排序，称以该成员数据项为关键字的排序。也可选择其中的若干个关键字为依据进行排序，先按主关键字进行排序，而主关键字相同的数据元素之间，再按次关键字进行排序……。②稳定排序：

指当两个数据元素关键字相同时，原来排在前的仍然排在前。常用排序方法：①插入排序

②选择排序

③冒泡排序3常用查找方法━━顺序查找顺序查找方法：指从第一个数据元素开始，依次顺序查找下去，直到找到要找的元素为止，或者一直找到最后一个元素也未找到。顺序查找函数模板：（保存在头文件“search.h”中）template<typenameT>intsequentSearch(TsL[],intn,Tk

)//在数组sL[n]中查找数据k{for(inti=0;i<n;i++)if(sL[i]

==

k)returni;//找到时，返回所找到元素的下标

return-1;//找不到时，返回-1

}4addr<<endl;}if(k!=i){temp=sL[i];sL[i]=sL[k];sL[k]=temp;}}for(i=0;i<8;i++)cout<<ps[i]<<endl;}直接插入排序函数模板（升序）：（保存在头文件“sort.{mid=(low+high)/2;cout<<“排序后━━通过索引学生资料为：\n”;#include“search.voidmain()折半查找（递归算法）函数模板：（保存在头文件“search.if(k<sL[mid])mid=binarySearch2(sL,low,mid-1,k);//递归调用16374156697478889299voidmain()cout<<setw(6)<<ps[i]->score;{char*ps[8]={“Youarestudent!”,“Beijing,China”,选择排序的基本思想（升序）：每一趟从待排序的元素中选出最小的元素，顺序放在已排好序的子序列的后面，直到全部元素都被选出并排好序。插入排序法━━直接插入【例】（对函数sequentSearch()进行测试。）#include<iostream.h>#include<stdlib.h>#include“search.h”voidmain(){inta[10],k;cout<<“数组中的数据为：\n”;for(inti=0;i<10;i++){a[i]=rand()%90+10;cout<<a[i]<<“”;}cout<<endl;cout<<“请输入要查找的数据：”;cin>>k;i=sequentSearch<int>(a,10,k);if(

i!=-1)cout<<a[i]<<“已找到，下标=”<<i<<endl;elsecout<<k<<“未找到!\n”;}

第一次运行：数组中的数据为：51274450997458286284请输入要查找的数：

66↙66未找到！第二次运行：数组中的数据为：51274450997458286284请输入要查找的数：

99↙99已找到，下标=45常用查找方法━━折半查找（二分法查找）折半查找的前提条件：数组必须有序，才能使用折半查找。折半查找方法：（假设数组元素已升序排列）①设置查找区间：定义两个指针low、high分别指向数组的首、尾两个元素；

②折半取区间中点：若查找区间存在，即low<=

high，则：mid=(low+high)/2

③查找并缩小查找区间：若所要找的元素==

mid所指的元素，则：表示已找到，查找成功，结束！若所要找的元素

>

mid所指的元素，则：取low=mid+1，high不变，继续查找，重复②；若所要找的元素<

mid所指的元素，则：取high=mid-1，low不变，继续查找，重复②；

④查找失败：当low

>

high

仍未查找到，则：表示找不到，查找失败，停止！67478889299high=9mid=(5+9)/2=7low=4+1=5

16374156697478889299mid=(0+9)/2=4high=9low=0012345678988（查找成功例）16374156697478889299mid=(0+9)/2=4high=9low=0012345678916374156mid=(0+3)/2=1high=4-1=3

low=04156low=1+1=2high=3mid=(2+3)/2=256high=3low=3

mid=(3+3)/2=367（查找失败例）7常用查找方法━━折半查找（二分法查找）折半查找（迭代算法）函数模板：（保存在头文件“search.h”中）template<typenameT>intbinarySearch1(TsL[],intn,Tk

)//在数组sL[n]中查找数据k{intlow=0,high=n-1,mid;while(low<=high){mid=(low+high)/2;if(k==sL[mid])returnmid;//找到时，返回所找到元素的下标if(k<sL[mid])high=mid-1;//左缩查找区间elselow=mid+1;}//右缩查找区间

return-1;}

//找不到时，返回-18常用查找方法━━折半查找（二分法查找）折半查找（递归算法）函数模板：（保存在头文件“search.h”中）template<typenameT>//在数组sL[n]中下标区间low~high之间查找数据kintbinarySearch2(TsL[],intlow,inthigh,Tk

){intmid=-1;//找不到时，返回-1

if(low<=high)

{mid=(low+high)/2;if(k>sL[mid])mid=binarySearch2(sL,mid+1,high,k);//递归调用 if(k<sL[mid])mid=binarySearch2(sL,low,mid-1,k);//递归调用

}

returnmid;}9【例】（对函数binarySearch1()、binarySearch2()进行测试。）#include<iostream.h>#include“search.h”voidmain(){inta[6]={32,45,56,78,88,97},k;cout<<“数组中的数据为：”;for(inti=0;i<6;i++)cout<<a[i]<<“”;cout<<endl;cout<<“请输入要查找的数据：”;cin>>k;i=binarySearch1

<int>(a,6,k);if(

i!=-1)cout<<a[i]<<“已找到，下标=”<<i<<endl;elsecout<<k<<“未找到!\n”;i=binarySearch2

<int>(a,0,5,k);if(

i!=-1)cout<<a[i]<<“已找到，下标=”<<i<<endl;elsecout<<k<<“未找到!\n”;}

第一次运行：数组中的数据为：

324556788897请输入要查找的数据：

57↙57未找到！57未找到！第二次运行：数组中的数据为：

324556788897请输入要查找的数据：

78↙78已找到，下标=378已找到，下标=310插入排序法━━直接插入、折半插入插入排序的基本思想：每一趟依次将待排序元素中的首个元素有序地插入到其前面已排好序的子序列中，直到全部元素都被插入并排好序。直接插入排序：当插入第i个元素时，其前面的第0~i-1个元素子序列已排好序，只需将要插入的元素与其前面子序列中的元素从后向前依次顺序比较，找到插入点并将其插入。折半插入排序：就是在寻找插入点的时候，用折半查找取代顺序查找。折半插入优于直接插入，它利用了数据元素排列中的部分有序性。11插入排序法━━直接插入直接插入排序过程（升序）：设数组为：a[0]a[1]…a[6]a[7]；

①第1趟插入：初始时已排好序的子序列为：a[0]；要插入的元素是：a[1]；将a[1]与a[0]比较，若a[0]小，则将a[1]插入在其后，否则反之。第1趟后，子序列a[0]a[1]已排好序，待排序的元素减缩为：a[2]~a[7]；

②第2趟插入：已排好序的子序列为：a[0]a[1]；要插入的元素是：a[2]；将a[2]依次与a[1]、a[0]比较，找到第一个比a[2]小的，则a[2]插入在其后。第2趟后，子序列a[0]a[1]a[2]已排好序，待排序的元素减缩为：a[3]~

a[7]；③……经过7趟插入后：a[0]a[1]…a[6]a[7]全部排好序。12mid=(0+9)/2=4直接插入排序函数模板（升序）：（保存在头文件“sort.【例】（对直接插入排序函数insertSort()进行测试。数组中的数据为：324556788897mid=(2+3)/2=2if(k==sL[mid])returnmid;//找到时，返回所找到元素的下标cout<<“排序前：”<<c<<endl;cout<<endl;排序前：5127445099745828template<typenameT>Beijing,China冒泡排序的基本思想（升序）：每一趟都从待排序元素区域的底部开始，相邻两个元素进行比较，小的元素交换到上方，大的元素交换至下方，这样一趟比较下来，最小元素已冒泡到该区域的最上方；①当待排序的每个数据元素其个体较大，排序过程中数据元素之间需要较大规模的交换移动，且需要在较大范围的内存中进行，这种情况下可考虑使用索引排序。cout<<“请输入要查找的数据：”;cin>>k;for(j=i+1;j<4;j++)①第1趟选择：初始时待排序的元素为：a[0]a[1]…a[6]a[7]；第6章(2)

━━顺序表的排序和查找i=binarySearch2<int>(a,0,5,k);16374156697478889299if(k==sL[mid])returnmid;//找到时，返回所找到元素的下标cout<<setw(6)<<ps[i]->score;for(j=i+1;j<n;j++)//从待排序的元素中选出最小元素，其下标存入k，值存入temp{char*ps[8]={“Youarestudent!”,“Beijing,China”,排序前：1a2b3c4d5e6f7g【例】（对函数binarySearch1()、binarySearch2()进行测试。template<typenameT>cout<<setw(14)<<ps[i]->addr<<endl;}插入排序的基本思想：每一趟依次将待排序元素中的首个元素有序地插入到其前面已排好序的子序列中，直到全部元素都被插入并排好序。cout<<setw(6)<<ps[i]->score;template<typenameT>插入排序法a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]第１趟插入[81]761792452116第２趟插入[7681]1792452116第３趟插入[177681]92452116第４趟插入[9177681]2452116第５趟插入[917247681]52116第６趟插入[5917247681]2116第７趟插入[591721247681]16[59161721247681]13插入排序法━━直接插入直接插入排序函数模板（升序）：（保存在头文件“sort.h”中）template<typenameT>voidinsertSort(TsL[],intn){inti,j;Ttemp;for(i=1;i<n;i++){temp=sL[i];//插入的元素先放到temp中，这样插入前各元素后移时可将该元素冲掉j=i; while(j>0&&sL[j-1]>temp

)//查找第一个比temp小的元素，temp将插入在其后{sL[j]=sL[j-1];//查找、移动位置同时进行

j--;}sL[j]=temp;}//插入temp

}14【例】（对直接插入排序函数insertSort()进行测试。）#include<iostream.h>#include<stdlib.h>#include“sort.h”voidmain(){chara[10];for(inti=0;i<10;i++)a[i]=rand()%26+65;cout<<“排序前：”;for(i=0;i<10;i++)cout<<a[i]<<“”;cout<<endl;insertSort<char>(a,10);cout<<“排序后：”;for(i=0;i<10;i++)cout<<a[i]<<“”;cout<<endl;}运行：排序前：

PHQGHUMEAY排序后：

AEGHHMPQUY15插入排序法━━折半插入折半插入排序函数模板（升序）：（保存在头文件“sort.h”中）template<typenameT>voidbinaryInsertSort(TsL[],intn){intlow,high,mid,i,j;Ttemp;

for(i=1;

i<n;i++)

{temp=sL[i];low=0,high=i-1;

while(low<=high)//折半查找插入点的位置{mid=(low+high)/2; if(temp<sL[mid])high=mid-1;elselow=mid+1;}for(j=i-1;j>=low;j--)sL[j+1]=sL[j];//移动元素，空出插入点的位置sL[low]=temp;}

//插入temp}16【例】（对折半插入排序函数binaryInsertSort()进行测试。）#include<iostream.h>#include<iomanip.h>#include“sort.h”voidmain(){floata[6]={3.4,-2.8,7.9,-5.6,9.8,8.8};cout<<“排序前：”;for(inti=0;i<6;i++)cout<<setw(6)<<a[i];cout<<endl;

binaryInsertSort<float>(a,6);cout<<“排序后：”;for(i=0;i<6;i++)cout<<setw(6)<<a[i];cout<<endl;}}运行：排序前：

排序后：

17选择排序法选择排序的基本思想（升序）：每一趟从待排序的元素中选出最小的元素，顺序放在已排好序的子序列的后面，直到全部元素都被选出并排好序。选择排序过程（升序）：设数组为：a[0]a[1]…a[6]a[7]；

①第1趟选择：初始时待排序的元素为：a[0]a[1]…a[6]a[7]；从中选择出最小的元素，并将该元素与a[0]元素互相交换；经过第1趟后，数组a中最小元素已排在0号位，子序列a[0]已排好序。②第2趟选择：待排序的元素减缩为：a[1]a[2]…a[6]a[7]；从中选择出最小的元素，并将该元素与a[1]元素互相交换；经过第2趟后，数组a中次小元素已排在1号位，子序列a[0]a[1]已排好序。③……经过7趟选择后：a[0]a[1]…a[6]a[7]全部排好序。18选择排序法a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]第１趟选择[81761792452116]第２趟选择5[7617924812116]第３趟选择59[

177624812116

]第４趟选择5916[7624812117

]第５趟选择591617[24812176]第６趟选择59161721[812476]第７趟选择5916172124[8176]5916172124768119选择排序法选择排序函数模板（升序）：（保存在头文件“sort.h”中）template<typenameT>voidselectSort(TsL[],intn){inti,j,k;Ttemp;

for(i=0;i<n-1;i++)

{temp=sL[i];k=i;

for(j=i+1;j<n;j++)

//从待排序的元素中选出最小元素，其下标存入k，值存入temp

if(temp>sL[j]){temp=sL[j];k=j;} if(k!=i){temp=sL[i];sL[i]=sL[k];sL[k]=temp;}}}20【例】（对选择排序函数selectSort()进行测试。）#include<iostream.h>#include<string.h>#include“sort.h”voidmain(){charc[80];for(inti=1;i<=2;i++){cout<<“请输入一行字符：”;cin.getline(c,80);cout<<“排序前：”<<c<<endl;

selectSort<char>(c,strlen(c));cout<<“排序后：”<<c<<endl;}}}运行：请输入一行字符：1a2b3c4d5e6f7g↙排序前：

1a2b3c4d5e6f7g排序后：

1234567abcdefg请输入一行字符：aAbBcCdDeEfFgG↙排序前：

aAbBcCdDeEfFgG排序后：

ABCDEFGabcdefg21冒泡排序法交换排序的基本思想：按关键字两两比较顺序表中元素，如果发生逆序则交换之，直到所有元素都排好序为止。冒泡排序的基本思想（升序）：每一趟都从待排序元素区域的底部开始，相邻两个元素进行比较，小的元素交换到上方，大的元素交换至下方，这样一趟比较下来，最小元素已冒泡到该区域的最上方；接着缩小待排序的元素区域，按同样方法从底部开始，继续下一趟的两两比较和交换；若在某一趟的比较中没有发生任何元素交换，则说明所有元素都已经排好序。冒泡排序的优点：利用了原来数据元素排列中的部分有序性。22冒泡排序法冒泡排序过程（升序）：设数组为：a[0]a[1]…a[6]a[7]；

①第1趟冒泡：初始时待排序的元素为：a[0]a[1]…a[6]a[7]；从底部a[7]、a[6]开始，两两比较，小上大下，直至最小元素冒泡到a[0]；经过第1趟后，数组a中最小元素已排在0号位，子序列a[0]已排好序。②第2趟冒泡：待排序的元素减缩为：a[1]a[2]…a[6]a[7]；从底部a[7]、a[6]开始，两两排序，直至该组最小元素冒泡到a[1]；经过第2趟后，数组a中次小元素已排在1号位，子序列a[0]a[1]已排好序。③……经过7趟冒泡后：a[0]a[1]…a[6]a[7]全部排好序。23冒泡排序法a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]第１趟冒泡[81761792452116]第２趟冒泡5[8176179241621]第３趟冒泡59[

817617162421]第４趟冒泡5916[8176172124]第５趟冒泡591617[81762124]第６趟冒泡59161721[817624]第７趟冒泡5916172124[8176]5916172124768124冒泡排序法冒泡排序函数模板（升序）：（保存在头文件“sort.h”中）template<typenameT>voidbubbleSort(TsL[],intn){boolnoswap;inti,j;Ttemp;

for(i=0;i<n-1;

i++)

{noswap=true; //该趟冒泡初始，将未交换标志noswap置为真 for(j=n-1;j>i;j--)

//从底部往上冒泡

{ if(sL[j]<sL[j-1]){temp=sL[j];sL[j]=sL[j-1];sL[j-1]=temp; noswap=false;}}if(noswap)break;//本趟冒泡中若无任何交换，说明已全部有序，则终止算法}}25【例】（对冒泡排序函数bubbleSort()进行测试。）#include<iostream.h>#include<stdlib.h>#include<iomanip.h>#include“sort.h”voidmain(){inta[8];for(inti=0;i<8;i++)a[i]=rand()%90+10;cout<<“排序前：”;for(i=0;i<8;i++)cout<<setw(6)<<a[i];cout<<endl;

bubbleSort<int>(a,8);cout<<“排序后：”;for(i=0;i<8;i++)cout<<setw(6)<<a[i];cout<<endl;}}运行：排序前：

5127445099745828排序后：

272844505158749926索引排序与查找索引排序与查找：①当待排序的每个数据元素其个体较大，排序过程中数据元素之间需要较大规模的交换移动，且需要在较大范围的内存中进行，这种情况下可考虑使用索引排序。②对待排序的每个数据元素都建立一个索引值，就形成了索引表，这样对原表数据元素的排序就转化成对其索引表的排序。③通常将每一个数据元素的起始地址作为其索引值，这样形成的索引表就是一个指针数组，而索引表中的元素就是指向原表中相应数据元素的指针。④引入索引表后，可实现索引查找，即先在索引表中查找，找到后再通过索引值得到其相应数据元素的具体信息。27【例】（使用索引排序，有若干学生数据，按成绩降序排序后输出。）学号姓名性别出生成绩住址61001方飞飞男1980/03/0596北京61002巩浩文女1981/06/1572南京61003程可国女1980/01/1199南京61004麦宏岩男1982/11/1483北京索引●●●●原数据表索引●●●●排序前索引表（排序前的指针指向）排序后索引表（按成绩排序后的指针指向）28【例】（使用索引排序，有若干学生数据，按成绩降序排序后输出。）#include<iostream.h>#include<iomanip.h>structStudent{intid; charname[10]; charsex[4]; charbirth[12]; intscore; charaddr[12];};voidmain(){Students[4];inti,j;

Student*ps[4],*temp;for(i=0;i<4;i++)

ps[i]=&s[i];//建立索引表cout<<“请输入四位学生的学号、姓名、性别、出生、成绩、住址：\n”;for(i=0;i<4;i++){cin>>s[i].id>>s[i].name>>s[i].sex;cin>>s[i].birth>>s[i].score>>s[i].addr;}29cout<<“排序前━━学生资料表内容为：\n”;for(i=0;i<4;i++){cout<<setw(8)<<s[i].id;cout<<setw(12)<<s[i].name;cout<<setw(6)<<s[i].sex;cout<<setw(16)<<s[i].birth;cout<<setw(6)<<s[i].score;cout<<setw(14)<<s[i].addr<<endl;}

for(i=0;i<3;i++)

//对索引表进行选择排序for(j=i+1;j<4;j++)if(ps[i]->score<ps[j]->score){temp=ps[i];

ps[i]=ps[j];

ps[j]=temp;}

30

cout<<“排序后━━通过索引学生资料为：\n”;for(i=0;i<4;i++){cout<<setw(8)<<ps[i]->id;cout<<setw(12)<<ps[i]->name;cout<<setw(6)<<ps[i]->sex;cout<<setw(16)<<ps[i]->birth;cout<<setw(6)<<ps[i]->score;cout<<setw(14)<<ps[i]->addr

<<endl;}

cout<<“排序后━━学生资料表内容为：\n”;for(i=0;i<4;i++){cout<<setw(8)<<s[i].id;cout<<setw(12)<<s[i].name;cout<<setw(6)<<s[i].sex;cout<<setw(16)<<s[i].birth;cout<<setw(6)<<s[i].score;cout<<setw(14)<<s[i].addr<<endl;}}运行：请输入学号、姓名、性别、出生、成绩、住址：61001方飞飞男1980/03/0596北京↙61002巩浩文女1981/06/1572南京↙61003程可国女1980/01/1199南京↙61004麦宏岩男1982/11/1483