二分查找

​ 二分查找算法也称为折半搜索、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。算法是建立在有序数组基础上的。时间复杂度: T(n) = Θ(logn)。

原理及实现

基本原理:使用递归、分治的思想

  • ① 当数组为空时,说明数组中不存在需查找的元素。
  • ② 用有序数组的中间位置元素与需查找元素进行大小比较,如果相等,则查找结束。
  • ③ 如果中间位置元素大于需查找元素,则从数组左侧位置进行递归查找。
  • ④ 如果中间位置元素小于需查找元素,则从数组右侧位置进行递归查找。

阅读全文

归并排序

​ 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。需要额外的存储空间,时间复杂度: T(n) = Θ(nlgn)。

阅读全文

插入排序

​ 每次将一个待排序的记录,按其大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。时间复杂度 T(n) = Θ(n²)。

原理及实现

基本原理:对待排序数组a[n],假设第i(i∈[1,n])个元素左侧已排序,右侧未排序。

  • ① 从i位置左侧已排序数组位置中,逆序遍历,查找元素a[i]的目标位置,即第一个比a[i]小的元素后边targetPos(或者第一个位置)。
  • ② 移动元素:将数组元素[targetPos + 1 .. i - 1] 整体向后移动一位。
  • ③ 将第i(i∈[1,n])个元素a[i]放置到[targetPos + 1]位置。
  • ④ 遍历执行①、②、③操作,直到最后一个元素a[n]。

阅读全文