查找与排序技术.ppt

1、查找 排序,查找与排序技术,查找,查找：查找是在一个给定的数据结构中，根据给定的条件查找满足条件的结点。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。 查找的结果： 查找成功：找到满足条件的结点 查找失败：找不到满足条件的结点。,查找的基本概念,关键字:是数据元素中可以唯一标识一个数据元素的数据项，比如学号、身份证号等。 查找:是根据给定的关键值，在一组数据中确定一个其关键字等于给定值的数据元素的过程。 确切定义：给定一个值K，在含有n个记录的文件中进行搜索，寻找一个其关键字等于给定的K值的记录，如找到，则输出记录或记录在文件中的相对位置称查找成功；否则输出查找不成功的信

2、息称查找失败。,查找方法,1.顺序查找 2.二分法查找 3.分块查找 4.散列（HASH）查找,查找方式与特点： 可以采用从前向后查，也可采用从后向前查的方法。 在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度较大。 在下面两种情况下只能采取顺序查找： a. 线性表为无序表（元素排列是无序的）； b. 即使是有序线性表，但采用的是链式存储结构。,顺序查找（线性查找） 查找过程： 对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。,1 . 线性表在顺序存储结构下的顺序查找 数据结构： typedef stru

3、ct int key; float info; SSTable;,顺序查找的算法： int Search_seq(SSTable ST , int n, int key) int i=n; ST0.key=key; while(STi.key!=key) i-； /*从表尾往前查*/ return i; ,监视哨,使用了监视哨，在查找过程中，不用每一步都去判断是否查找结束。 找到：返回元素在线性表中的存储位置； 未找到：返回0。,根据上述算法可知： 查找成功时的平均查找次数为： ASL=(1+2+3+4+n)/n=(n+1)/2 查找不成功时的比较次数为： n+1 则顺序查找的平均查找长度为：

4、 ASL=(n+1)/2+n+1)/2=(n+1)3/4 顺序查找的优点：算法简单，无需排序，采用顺序和链式存储均可。 缺点：平均查找长度较大。,2. 线性表在链式存储结构下的顺序查找 struct node int data; struct node *next; ; int searlb(struct node *h,int x) struct node *m; m=h; while(m-next!=NULL ,折半查找（二分法查找） 思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。 前提：必须在具有顺序存储结构的有序表中进行。,查找过程： 1）若中间项

5、的值等于x,则说明已查到。 2）若x小于中间项的值，则在线性表的前半部分查找。 3）若x大于中间项的值，则在线性表的后半部分查找。 特点：比顺序查找方法效率高。最坏的情况下，需要比较log2n次。,查找23和79的过程如下图：,mid=(low+high)/2 （只舍不入）,( 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,

6、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 ),折半查找的算法程序： int Search_Bin( SSTable ST , int n, int key) int low, high,mid; low=1; high=n; while(low=high) mid=(low+high)/2; if(STmid.key=key) return(mid); /*查找成功*/ else if(keySTmid.key) hig

7、h=mid-1; /*在前半区间继续查找*/ else low=mid+1; /*在后半区间继续查找*/ return (0); /*查找不成功*/ ,主程序：在数组中存放学生的学号和姓名，程序根据输入学号，使用折半查找法查找学生信息。 #include typedef struct int no; char name10; Sstable; main( ) int no, j; int Search_Bin( Sstable ST , int n, int key) ; Sstable pp5=0,”0”,1,“赵刚”,2,“钱红”,3,“孙波”, 4,“李朋”; /*pp0未用*/ sca

8、nf(“%d”, /*查找不成功*/,运行： 输入：3 结果：The name is 孙波 输入：5 结果： No number,分块查找,要求文件中记录关键字“分块有序”,即前一块中最大关键字小于后一块中最小关键字,而块内的关键字不一定有序。 分块查找的基本思想 ：先抽取各块中的最大关键字构成一个索引表，由于文件中的记录按关键字分块有序，则索引表呈递增有序状态。查找分两步进行:第一步先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块，第二步在已限定的那一块中进行顺序查找。 用分块查找的文件不一定分成大小相等的若干块，块大小及其分法可根据文件的特征来定。分块查找不仅适用于顺序方式存储的顺

9、序表，也适用于线性链表方式存储的文件。,索引表,块中的最大关键字,块内第一个记录位置的指针,分块查找分两步进行：先查索引表（索引表表长较短用顺序查找，较长可用折半查找）确定记录在哪一块。然后在相应的块中查找。例:查找12，由索引表的第一项知，记录要么在第一块中，要么不存在，由此取到第一块中第一个记录位置。接着在第一块中进行顺序查找。分块查找效率高于顺序查找，但低于折半查找。,散列（HASH）查找 直接查找技术 直接查找技术的含义： 设表的长度为n，如果存在一个函数i=i(k),对于表中的任意一个元素的关键字k，满足以下条件： （1）1in。 （2）对于任意的元素关键字k1k2，恒存在i(k1)

10、i(k2)。 则称此表为直接查找表。其中函数i=i(k)称为关键字k的映像函数。 2. 直接查找表的操作： （1）直接查找表的填入 （2）直接查找表的取出 3.直接查找表中各元素的存储地址: 直接查找表的首地址（i1）m 其中：m是各元素在存储空间中所占的字节。 i=i(k)。,例： 将关键字序列（09，31，26，19，01，13，02，11，27，16，05，21）依次填入长度为n12的表中。设映像函数为i=INT(K/3)+1,其中INT为取整符。,结论：为了有效地使用散列技术，需要解决以下两方面的问题 构造好的哈希函数，使冲突的现象尽可能的少。 设计有效的解决冲突的方法。,散列（HAS

11、H）查找 查找思想： 根据关键字的值，利用某个函数直接计算出元素所在的位置（也称杂凑） 。 2. 基本概念 哈希函数：根据关键字而直接计算出元素所在位置的函数,常用H表示。 冲突：两个不同的关键字K1和K2计算出相同的存储位置的现象称为冲突， K1和K2互为同义词。 哈希表：哈希表是一种存储结构，叫散列存储。是通过哈希函数和解决冲突的办法把键值存放在哈希表中。 3. 主要目标: 是提高查找效率，即缩短查表和填表的时间。,构造哈希函数的方法 （1） 直接定址法取关键字或关键字的某个线性函数值为散列地址，即 H（K）=K 或 H（K）=A*K+B；（其中A、B为常数） 例：某公司一险种投保费交纳表

12、（20年），将年份作关键字，哈希函数取关键字本身，若查找第3年应交纳的保费，只要查找表的第3项即可。,（2）平方取中法取关键字平方后的中间几位为哈希函数。 如：K=308，K2=94864，H（K）=486,（3） 除后余数法取关键字被不大于散列表表长m的数p除后所得的余数为哈希地址。 即 H（K）=K MOD p （pm）,处理冲突的方法 （1） 开放定址法,设散列函数 H（k）=k MOD m （m为表长, 设m=11) 若发生冲突，设发生冲突的地址为 p , 则沿着一个探查序列逐个探查，那么，探查的地址序列为 P+1, P+2, P+3 , m-1 , 0, 1, , P-1.,例如 :

13、 在长度为11的散列表中，已填有关键字分别为60、17、29的记录，现填入第四个记录，其关键字为38。 由散列函数得散列地址为5，冲突，经过探测，比较，最后得到地址为8。38被填到哈希表中共比较了四次，探测了三次。,按开放地址法所建的散列表的散列查找算法： #define M 100 int h(int k) return (k%97); int SearchHase(int t ,int k) int i,j=0; i=h(K); /*求得哈希地址*/ while(jM /*查找不成功*/,缺点：关键字的不同散列函数值造成探测次数多，删除运算较难，溢出处理复杂。因此，在处理动态变化的表时最好

14、采用链地址法。,(2)链地址法 方法：把具有相同散列地址的键值存放在同一个链表中，称为同义词链表。 优点：插入、删除方便；缺点：占用存储空间多。,例：一组关键字为（21，14，19，58，65，32，72） H(K)=K MOD 11,排 序概 述,1、排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。 2、排序过程： 首先比较两个关键字的大小； 然后将记录从一个位置移动到另一个位置。 3、方法： 内排序 ：指当文件的数据量不太大时，全部信息放在内存中处理的排序方法。 外排序：当文件的数据量较大时，排序过程中需要在内、外存之间不断地进行数据交换才能达到排序的目的。

15、,假设待排序的记录存放在地址连续的一组存储单元中，那么这种存储方式下的数据类型可描述为：,MAX,0,1,2,3,4,key,info,#define MAX 20 typedef struct int key; float otherinfo; RedType;,基本的排序方法,1、交换排序 2、插入排序 3、选择排序 4、归并排序与基数排序 5、排序小结,插入排序,基本思想是：每步将一个待排序的记录，按关键码值的大小插入到前面已排序的适当位置上，直到全部插完为止。 1. 直接插入排序：在排好的序列中用顺序法查找插入位置，找到后将其后记录后移一个位置，插入新记录。排序n个记录的文件，关键码比

16、较次数为n2量级，记录移动个数也为n2量级。 2. 二分法插入排序：在已排好序的序列中使用二分法查找插入位置，找到后移动其后记录插入新记录。关键字比较次数降为nlog2n量级，记录移动个数仍为n2量级。 3.希尔排序：将整个无序序列分割成若干小的子序列分别进行插入排序。,直接插入排序,该算法适合于n 较小的情况，时间复杂度为O(n2).,待排元素序列：53 27 36 15 69 42 第一次排序： 27 53 36 15 69 42 第二次排序： 27 36 53 15 69 42 第三次排序： 15 27 36 53 69 42 第四次排序： 15 27 36 53 69 42 第五次排序

17、： 15 27 36 42 53 69 直接插入排序示例,对于有n个数据元素的待排序列，插入操作要进行n-1次,void InsertSort(RedType L , int n) int i , j; for(i=2; i=n; i+) if(Li.keyLi-1.key) L0=Li; /* 作为监视哨*/ for( j=i-1;L0.keyLj.key; j) Lj+1=Lj; /* 记录后移*/ Lj+1=L0; /* 插入 */ ,插入算法如下： 方法:Ki与Ki-1,K i-2,K1依次比较,直到找到应插入的位置。,折半插入排序（二分法插入排序）,(highlow ，查找结束，插入

18、位置为low 或high+1 ),( 4236 ),( 4253 ),例如，待排元素的关键字序列为： 15，27，36，42，53，69，80，30 在前7个记录都已排好序的基础上，利用折半插入法插入第8个记录的排序过程： 15 27 36 42 53 69 80 30 low mid high low mid high low mid high high low 15 27 30 36 42 53 69 80,( 30 42 ),( 30 27 ),( 30 36 ),(highlow ，查找结束，插入位置为low 或high+1 ),void BInsertSort(RedType L ,

19、int n) int i, low, high, mid; for(i=2; i=high+1; j ) Lj+1=Lj; /* 记录后移*/ Lhigh+1=L0; /* 插入*/ ,折半插入排序减少了关键字的比较次数，但记录的移动次数不变，其时间复杂度与直接插入排序相同。,/*折半后的位置*/,O(n2),选择排序,简单选择排序基本思想是：每次从待排序的记录中选出关键字最小(或最大)的记录，顺序放在已排序的记录序列的最后，直到全部排完为止。 堆排序的基本思想：通过调整建堆的方法，实现无序序列的排序过程。,1、简单选择排序 思想：首先从1n个元素中选出关键字最小的记录交换到第一个位置上。然后

20、再从第2 个到第n个元素中选出次小的记录交换到第二个位置上，依次类推。 时间复杂度为O(n2)， 适用于待排序元素较少的情况。,初态,8 3 9 1 6,8 3 9 1 6,8 3 9 1 6,8 3 9 1 6,1 3 9 8 6,1 3 9 8 6,1 3 9 8 6,简单选择排序的算法如下： void SelectSort( RedType L , int n) int i, j, k, t; for (i=1; i=n; +i） /*选择第i小的元素，并交换到位*/ k=i； for(j=i+1; j=n; +j) if ( Lj.keyLk.key) k=j; /*Lk 中存放的是第

21、i小的元素*/ if(k!=i) t=Li;Li=Lk; Lk=t ; /*交换*/ ,2、堆排序：也是一种选择排序。是具有特定条件的顺序存储的完全二叉树，其特定条件是：任何一个非叶子结点的关键字大于等于（或小于等于）子女的关键字的值。 (1) 堆的示例,(a):堆顶元素取最大值,(b):堆顶元素取最小值,(2) 实现堆排序需解决两个问题： 如何由一个无序序列建成一个堆？ 输出堆顶元素后，如何将剩余元素调整成一个新的堆？,(3) 输出堆顶元素并调整建新堆的过程 ( 筛选 ),把自堆顶至叶子的调整过程称为“筛选”。从一个无序序列建堆的过程就是一个反复“筛选”的过程。,（4）由无序序列建初始堆的过

22、程,(c): 49被筛选后的状态,(d): 56被筛选后的状态,(e): 被筛选之后建成堆,(25, 56, 49, 78, 11, 65, 41, 36),交换排序 基本思想是：两两比较待排序记录的关键码，并交换不满足顺序要求的偶对，直至全部满足为止。 交换排序的特点在于交换。有冒泡和快速排序两种。 起泡排序：将待排序的记录按从后向前的顺序顺次两两比较，若为逆序则进行交换。将序列照此方法从头到尾处理一遍称作一趟起泡，一趟起泡的效果是将关键码值最小的记录交换到了最前位置，即该记录的顺序起始位置。若某一趟起泡过程中没有任何交换发生，则排序过程结束。 快速排序：对冒泡排序的改进,交 换 排 序冒泡

23、排序,思想：小的浮起，大的沉底。从左端开始比较。 第一趟：第1个与第2个比较，大则交换；第2个与第3个比较，大则交换，关键字最大的记录交换到最后一个位置上； 第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换 到第n-1个位置上； 依次类推，则完成排序。 正序：时间复杂度为O(n) 逆序：时间复杂度为O(n2) 适合于数据较少的情况。 排序n个记录的文件最多需要n-1趟冒泡排序。,第 六 趟 排 序 后,第 五 趟 排 序 后,第 四 趟 排 序 后,第 三 趟 排 序 后,第 二 趟 排 序 后,第 一 趟 排 序 后,初 始 关 键 字,思想：小的浮起，大的沉底。,最 终 结 果

24、,冒泡排序的C程序段： Void BubbleSort ( RedType L , int n ) int i, x, j=1, k=1; while (j0); k=0; for (i=1; i=n-j; i+) if (Li+1.keyLi.key) k+;x=Li; Li=Li+1; Li+1=x; /*交换*/ j+; ,思想：通过一趟排序将待排序列分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分排序，以达到整个序列有序。 关键字通常取第一个记录的值为基准值。 做法：附设两个指针low和high ，初值分别指向第一个记录和最后一个记录，设关键字为 key ，首先从

25、high所指位置起向前搜索，找到第一个小于基准值的记录与基准记录交换，然后从low 所指位置起向后搜索，找到第一个大于基准值的记录与基准记录交换，重复这两步直至low=high为止。 时间复杂度：O(nlog2n),交 换 排 序快速排序,快速排序过程示意图：,有序序列 6 18 23 52 67,key,初始序列 23 52 6 67 18,low,high,一次交换 18 52 6 67 23,low,high,二次交换 18 23 6 67 52,high,三次交换 18 6 23 67 52 / 完成一趟排序后分别进行快速排序,low,high,2318,交换,2352,交换,2367, high=high-1,Low、high,low=low+1,high=high-1,236,交换,low=low +1,例题,归并排序,初始序列 23 52 67 6 18 10 一趟归并后 23 52