算法与数据结构基础
查找算法：
二分查找法：
简介：二分查找法又被称为折半查找法，用于预排序的查找问题
过程：
- 如果在列表a中查找元素t，先将列表a中间位置的项与查找关键字t比较，如果两者相等，则成功。
- 否则，将表分为前后两个子表
- 如果中间位置大于t，则进一步查找前一子表，否则，查找后一子表
- 重复上述过程
优劣：
- 时间复杂度为O(log~2~N),比较快
- 缺点就是必须是有序列表
排序算法：
冒泡排序
简介：两两比较大小，如果不满足升序关系，则交换
过程：略
优劣：：
- 时间复杂度为O(N^2^)，速度较慢
- 稳定
选择排序
简介：找出最小值，然后放入一个新的列表中
过程：略
优劣：：
- 时间复杂度为O(N^2^)，速度较慢
- 稳定
插入排序法
简介：依次检查需要排序的列表，每次取出一个元素放入另一个排好序的列表中的适当位置。
过程：略
优劣：：
- 时间复杂度为O(N^2^)
- 速度不稳定，最佳情况为线性增长，最差情况为N^2^,所以速度实际上比前两种快
归并排序
简介：分而制之的思想
过程：
- 将包含N个元素的列表分为两个含N/2元素的子列表.
- 对两个子列表递归调用归并排序(最后将两个子列表分解为N个子列表)。
- 合并已排序好的列表。
优劣：：速度较快且稳定，时间复杂度为O(Nlog~2~N)
实现代码:
def merge(left,right):
merged = []
i,j = 0,0
left_len,right_len = len(left),len(right)
while i<left_len and j<right_len:
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged
def mergeSort(a):
if len(a) <= 1:
return a
else:
mid = len(a) // 2
left = mergeSort(a[:mid])
right = mergeSort(a[mid:])
merge(left,right)
return merge(left,right)
def main():
a = [59,12,77,64,72,69,46,89,31,9]
a1 = mergeSort(a)
print(a1)
if __name__ == '__main__':
main()快速排序 #：
简介：对冒泡排序的改进
过程：
- 设置两个变量i和j，作为列表首末两端的下标，即i=0，j=N-1
- 设置列表的第一个元素作为关键数据，即key=A[0]
- 从j开始向前搜索，找到第一个小于key的值A[j],将A[j]和A[i]互换
- 从i开始向后搜索，找到第一个大于key的值A[i],将A[i]和A[j]互换
- 重复3~4步，直到i = j
优劣：：
- 平均情况时间复杂度为O(Nlog~2~N),比较快。
- 最差情况下时间复杂度为O(N^2^)
Python语言中提供的排序算法
内置数据类型list的方法sort()，内置函数sorted()
这个的底层实现就是归并排序，只是使用了Python无法编写的底层实现，从而避免了Python本身附加的大量开销,速度比我们自己写的归并排序要快很多（10~20倍）,所以说我们一般排序都尽量使用sorted和sort
