计算机储存海量数据,其优势之一就是能快速找到所需的内容,我们称这种能力为查找(searching)。在AP计算机A考试中,你需要掌握顺序查找折半查找

  • 顺序查找通常从数组或列表的第一个元素开始,逐一访问所有项目直至找到满足条件的值并返回索引位置、或查找到数组或列表的结尾仍未找到并返回-1
  • 折半查找仅能用于已被排序或按顺序储存的数据上。程序先检查数据的中段,看值是小于、等于还是大于查找标准,基于这个结果再进行进一步查找。每查找一轮,搜索的范围都减半。

如果希望对自然分布的数组或列表进行折半查找,如何做到呢?事实上有很多种排序算法。在AP计算机A考试中,你需要掌握以下这三种:

  • 选择排序——找到从当前位置到数组结束处的最小值,并与当前位置的元素交换。在索引0array.length - 2之间一直重复这个过程。你没有必要处理最后一个元素——在排序完成之后,它必然是整个数组的最大值。
  • 插入排序——将下一个未排序元素插入到已经排好序的部分,将更大的值均往右移一位。从索引1开始并对整个数组进行这种操作。
  • 归并排序——将元素分为两部分,再对每一部分继续进行递归分解。最后分解到两个元素的时候可以进行排序合并,再一直两两归并完成整个递归的过程。

陈 欣

AADPS创始人

发表评论