chapter 04_查找排序算法

《chapter 04_查找排序算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法（C语言描述）排序算法本章目标了解查找的基本方法了解内排序和外排序的基本概念理解内排序的分类掌握内排序各大算法的基本原理学会用C语言实现内排序各大算法查找算法顺序查找(O(n))顺序查找，直到找到符合条件的项(最基本的)二分查找(O(logn))要求必须按照关键字值的递增或递减的顺序排列分块查找()分成若干块，每一块中的元素存储顺序是任意的但是块与块之间必须按关键字大小有序排列。即前一块中的最大关键字小于后一块中的最小关键字值。哈希查找(需具体情况分析)对记录的关键字值进行运算，直接求出该记录文件的地址二分查找首先用要查找的关键字K与中间位置的结点的关键字相比较

2、，这个中间结点把线性表分成了两个子表，若比较结果相等则查找完成，若不相等，再根据K与该中间结点关键字的比较大小确定下一步查找哪个子表二分查找对有序表的查找，必须掌握时间复杂度O(log2N)二分查找具体算法实现•/****************************************************************•方法名://mid•描述://二分查找•参数://inta[]数组a•//key需要查找的值•//length数组长度•返回://-1为没有查找到，其他值为所要查找的值所在位置•******************************

3、**********************************/•intmid(inta[],intkey,intlength)•{•intlow,high,mid;•low=0;•high=length-1;•while(low<=high)•{•mid=(low+high)/2;•if(a[mid]==key)•{•returnmid;•}•if(key>a[mid])•{•low=mid+1;•}•else•{•high=mid-1;•}•}•return-1;•}分块查找分块查找又索引查找，它主要用于“分块有序”表的查找。所谓“分块有序”是指将线性表L（一维数组

4、）分成m个子表（要求每个子表的长度相等），且第i+1个子表中的每一个项目均大于第i个子表中的所有项目。“分块有序”表应该包括线性表L本身和分块的索引表A。因此，分块查找的关键在于建立索引表A。线性表L（有序）为：123456789101112分成m=3个子表：{1234}{5678}{9101112}（1）索引表A：二维数组：第一列为每个子表的最大值，第二列为每个子表的起始地址即：4084128（2）利用索引表A，确定待查项X所在的子表（块）。（3）在所确定的子表中可以用“折半查找”法搜索待查项X；若找到则输出X；否则输出未找到信息。时间复杂度哈希查找哈希查找是通过计算数据元

5、素的存储地址进行查找的一种方法。哈希查找的操作步骤：⑴用给定的哈希函数构造哈希表；直接地址法，除留余数法等⑵根据选择的冲突处理方法解决地址冲突；开放地址法例：{19,01,23,14,55,20,84,27,68,11,10,77}0-18地址空间中队关键字序列构造哈希表。哈希函数为H(key)=key%13链地址法{87,25,310,08,27,132,68,95,187,123,70,63,47}散列函数为H(k)=k%13⑶在哈希表的基础上执行哈希查找。时间复杂度为(O(1))影响因素：哈希函数，处理冲突的方法，装填因子。内排序和外排序若整个排序过程不需要访问外存便能

6、完成，则称此类排序问题为内部排序;若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，排序需要借助外部存储设备才能完成，则称此类排序问题为外部排序。这两个不是数据结构，而是依据排序过程使用到的存储器类型不同对排序算法分的类。排序是算法问题，很显然，无论内部还是外部排序，都是用于排序的。内排序的分类内排序的分类分为五大类：1、插入排序：包括直接插入排序O(n^2)希尔排序O(nlogn)～O(n^2)2、交换排序：包括冒泡排序O(n^2)快速排序O(nlogn)3、选择排序：包括选择排序O(n^2)堆排序O(nlogn)4、归并排序：O(nlogn)5、基数排序：O

7、(n)直接插入排序原理：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。要点：设立哨兵，作为临时存储和判断数组边界之用。时间复杂度O(n^2)直接插入排序•voidinsertSort(intarray[],intn)•{•inti,j;•inttemp;•for(i=1;i0&&temp