​ 二分查找算法也称为折半搜索、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。算法是建立在有序数组基础上的。时间复杂度： 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]。