(39)--公共基础计算机二级Office高级应用.ppt

《(39)--公共基础计算机二级Office高级应用.ppt》由会员分享，可在线阅读，更多相关《(39)--公共基础计算机二级Office高级应用.ppt（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、七、查找技术七、查找技术1、查找的概念:n在一个给定的数据结构中查找指定的元素2、查找的分类n顺序查找n比较的次数最坏情况下为n次4.1.4查找与排序查找与排序13 826381751344.1.4查找与排序查找与排序n二分法查找n二分查找的前提：数据必须是有序的。数据必须是有序的。n比较次数最坏情况下为log2n次8 1317263438513、查找的注意事项n如采用顺序存储n如果是有序线性表有序线性表，则可以采用二分法查找或顺序查找n二分查找最坏查找次数为二分查找最坏查找次数为：loglog2 2n n次次n顺序查找最坏查找次数为：顺序查找最坏查找次数为：n n次次；n如果是无序的如果是无

2、序的只能用顺序查找，n最坏查找次数为：n次。4.1.4查找与排序查找与排序4.1.4查找与排序查找与排序n如采用链式存储n不管数据是有序的还是无序的，则只能采用顺序查找n最坏查找次数为：n n次次八、排序技术八、排序技术1、交换类排序、交换类排序n冒泡排序法：最坏比较次数为n(n-1)/2n快速排序法：是对冒泡排序的改进，最坏比较次数为O(nlog2n)4.1.4查找与排序查找与排序13 826381751342、插入类排序、插入类排序n简单插入排序法n最坏情况需要n(n-1)/2次比较；n希尔排序法n最坏情况需要o（n 1.5）次比较。4.1.4查找与排序查找与排序3、选择类排序：、选择类排序：n简单选择排序法n最坏情况需要n(n-1)/2次比较；n堆排序法n最坏情况需要o（nlog2 n）次比较。4.1.4查找与排序查找与排序 下课了。下课了。追求追求休息一会儿。休息一会儿。