二分查找 二分查找又叫折半查找，是在有序列表的基础上进行查找，每次查找可以筛掉一半的元素。 算法步骤 以升序数列$L[0…n-1]$为例，假设要查找的数为$x$： 让$x$与数列中间位置的元素$L[\lfloor \frac n2 \rfloor]$进行比较，如果相等则返回该元素下标，否则： 如果$x$比中间元素小，递归地对中间元素左边的数列（比二分查找小的元素）进行二分查找； 如果$x$比中间元素大，递归地对中间元素右边的数列（比二分查找大的元素）进行二分查找。 代码实现 Python实现 递归实现： 1def BinarySearch(arr, target, left = 0, right = 0): 2 """二分排序（递...

经典字符串匹配 BF暴力匹配算法 暴力匹配，即Brute Force，简称BF算法。BF算法是一种简单朴素的模式匹配算法，常用于在一个主串S内查找一个子串T的出现位置。 算法步骤 假设有主串S与子串P，主串S的长度为N，子串T的长度为M。 将S和T左对齐，并比较其第一个元素。 若匹配，则继续比较下一个元素，一直到第M个元素。 若不匹配则T向右移动一个位置。 接着根据步骤3和4进行比较，直到匹配到或者T移动了N-M且仍未匹配到。 代码实现 Python实现 实现1： 1def BFMatch(s, p): 2 if len(s) < len(p): 3 return -1 4 i, j = 0, 0 5 # 匹配阶段 6 while...

临时变量 通过建立一个临时变量来实现两数交换： 1def swap(x, y): 2 print(x, y) 3 tmp = x 4 x = y 5 y = tmp 6 print(x, y) 7 return x, y 8 9if __name__ == '__main__': 10 swap(1, 2) 缺点： 需要消耗额外的内存。 优点： 不限制类型，大多数类型都能使用该操作。 加减交换 通过加减法实现： 1def swap(x, y): 2 print(x, y) 3 x = x + y 4 y = x - y 5 x = x - y 6 print(x, y) 7 return x, y 8 9if __name__...

冒泡排序 冒泡排序（Bubble Sort）是一种简单直观的排序算法。 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 时间复杂度：$O(n^2)$ 算法步骤 假设一个序列长度为n，m（m≤n）是已排序完成的在末尾的数。 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。对比结束后，最后的元素会是最大的数。 对接下来n-m个未排序的数重复步骤1和2，直到没有任何一对数字需要比较。 第一趟对序列中所有n个数进行比对，第二趟对序列中n-1个未排序完成的数进行比对，以此类推。每次比对的数为n-m。 动画演示： 代码实现 Python实现 1def...