无论是任何程序员, 不论是算法, 还是其他, 都需要掌握一定的数据结构. 本文以最优雅的方式, 基于 Python, 完成算法, 不要问, 背下来就好. 代码量更少, 更好背.
源码:
第 1 篇 查找和排序: 二分查找, 冒泡排序, 选择排序, 插入排序, 希尔排序, 归并排序, 快速排序.
1. 二分查找
二分查找, 时间复杂度 O(logn), 排序一次, 查找多次, 排序成本可以忽略; 只查找一次, 则顺序查找比较好. 非递归 13 行, 递归 11 行.
- def binary_search(alist, item):
- """
- 二分查找, 非递归
- 1. 2 个参数, 待查找 alist 和查找项 item
- 2. 声明 3 个变量, first,last,found(返回值)
- 3. while 条件, first 小于等于 last,found 是 false
- 4. mid 是 first 和 last 的中值 (整除);
- 5. 三个 if 条件, 相等 alist[mid]=item, 小于中值换 last, 大于中值换 first;
- 6. 返回 found,13 行
- :param alist: 待查找 alist
- :param item: 待查找项 item
- :return: 是否找到
- """
- first = 0
- last = len(alist) - 1
- found = False
- while first <= last and not found:
- mid = (first + last) // 2
- if alist[mid] == item:
- return True
- else:
- if item <alist[mid]:
- last = mid - 1
- else:
- first = mid + 1
- return found
- def binary_search_re(alist, item):
- """
- 二分查找, 递归
- 1. if 终止条件, 长度为 0, 返回 False;
- 2. 中点是长度除 2, 中值判断;
- 3. 小于递归前半部分, 大于递归后半部分, 返回递归函数;
- 4. 11 行
- :param alist: 待查找 alist
- :param item: 待查找项 item
- :return: 是否找到
- """
- if len(alist) == 0:
- return False
- else:
- mid = len(alist) // 2
- if alist[mid] == item:
- return True
- else:
- if item < alist[mid]:
- return binary_search_re(alist[:mid], item)
- else:
- return binary_search_re(alist[mid + 1:], item)
- def test_of_binary_search():
- test_list = [0, 1, 2, 8, 13, 17, 19, 32, 42]
- print(binary_search(test_list, 3))
- print(binary_search(test_list, 13))
- print(binary_search_re(test_list, 3))
- print(binary_search_re(test_list, 13))
- if __name__ == '__main__':
- test_of_binary_search()
- 2. 冒泡排序
- 冒泡排序, 时间复杂度 O(n^2), 冒泡排序通常被认为是低效的排序方式. 优势是: 识别排序列表, 和提前终止排序. 冒泡排序 4 行, 短冒泡排序 9 行.
- def bubble_sort(alist):
- """
- 冒泡排序
- 1. 两次遍历, 第 1 次遍历长度, 倒序逐渐减 1, 每遍历一次, 排序一个;
- 2. 第 2 次, 正常遍历, 少 1 个值, 因为 i 和 i+1;
- 3. 当前位大于下一位, 交换当前位和下一位;
- 4. 4 行
- :param alist: 待排序列表
- :return: None, 内部排序
- """
- for p_num in range(len(alist) - 1, 0, -1):
- for i in range(p_num):
- if alist[i]> alist[i + 1]:
- alist[i], alist[i + 1] = alist[i + 1], alist[i]
- def short_bubble_sort(alist):
- """
- 短冒泡排序, 增加 exchange, 额外终止参数
- 1. 初始为 True, 当为 False 时终止;
- 2. 在第 2 次循环前, 设置为 False, 交换一次就设置为 True, 一次未交换则触发终止;
- 3. 9 行, 增加 5 行的 exchange 操作
- :param alist:
- :return:
- """
- exchange = True
- for p_num in range(len(alist) - 1, 0, -1):
- if not exchange:
- break
- exchange = False
- for i in range(p_num):
- if alist[i]> alist[i + 1]:
- alist[i], alist[i + 1] = alist[i + 1], alist[i]
- exchange = True
- def test_of_bubble_sort():
- alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
- # bubble_sort(alist)
- # print(alist)
- alist = [17, 20, 26, 93, 77, 31, 44, 55, 54]
- short_bubble_sort(alist)
- print(alist)
- if __name__ == '__main__':
- test_of_bubble_sort()
- 3. 选择排序
- 选择排序, 时间复杂度 O(n^2), 比较次数与冒泡排序相同, 交换次数小于冒泡排序. 选择排序 6 行.
- def selection_sort(alist):
- """
- 选择排序, 即选择最大值再交换
- 1. 依然是 2 次遍历, 第 1 次反序, 第 2 次正序, 注意起始为 1, 末尾 + 1;
- 2. max_loc 存储最大值, 默认第 0 位;
- 3. 当 loc 的值大于 max_loc 的值时, max_loc 重新赋值;
- 4. 交换 loc 和 max_loc
- 5. 6 行
- :param alist: 待排序 alist
- :return: None
- """
- for p_num in range(len(alist) - 1, 0, -1):
- max_loc = 0
- for loc in range(1, p_num + 1):
- if alist[loc]> alist[max_loc]:
- max_loc = loc
- alist[p_num], alist[max_loc] = alist[max_loc], alist[p_num]
- def tes_of_selection_sort():
- alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
- selection_sort(alist)
- print(alist)
- if __name__ == '__main__':
- tes_of_selection_sort()
- 4. 插入排序
- 插入排序, 时间复杂度 O(n^2), 用移位代替交换, 移位操作的时间大约是交换时间的 1/3. 插入排序 7 行.
- def insert_sort(alist):
- """
- 插入排序,
- 1. 遍历列表, 存储当前值 cur_val, 设置游标 pos
- 2. 游标大于 0 和游标的值大于当前值, 则移位, 同时游标减 1;
- 3. 将当前值赋予游标的终止位置;
- 4. 7 行
- :param alist: 待排序 alist
- :return: None
- """
- for idx in range(1, len(alist)):
- cur_val = alist[idx]
- pos = idx # 游标
- while pos> 0 and alist[pos - 1]> cur_val:
- alist[pos] = alist[pos - 1]
- pos -= 1
- alist[pos] = cur_val # 最后游标的位置
- def test_of_insert_sort():
- alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
- insert_sort(alist)
- print(alist)
- if __name__ == '__main__':
- test_of_insert_sort()
- 5. 希尔排序
- 希尔排序, 时间复杂度, 介于 O(n)~O(n^2), 也可以认为是 O(n^3/2), 插入排序的改进, 比较和移位较少, 每次遍历都会生成一个 "更有序" 的子列表. 12 行, 增量部分 5 行, 插入部分 7 行.
- def shell_sort(alist):
- """
- 希尔排序
- 1. 两部分, 第 1 部分, 计算增量 gap 和起始位置 s_pos;
- 2. 增量是累除 2,s_pos 是增量的遍历
- 3. 增量插入排序, 额外传入起始位置和增量;
- 4. range 的起始由起始位置 + 增量;
- 5. 循环条件为大于等于增量, 差值为增量
- 6. 12 行, 增量部分 5 行, 插入部分 7 行
- :param alist: 待排序 alist
- :return: None
- """
- gap = len(alist) // 2
- while gap> 0:
- for s_pos in range(gap):
- gap_insert_sort(alist, s_pos, gap)
- gap = gap // 2
- def gap_insert_sort(alist, s_pos, gap):
- """
- 带增量的插入排序
- :param alist: 待排序 alist
- :param s_pos: 起始位置
- :param gap: 增量
- :return: None
- """
- for idx in range(s_pos + gap, len(alist), gap):
- cur_val = alist[idx]
- pos = idx
- while pos>= gap and alist[pos - gap]> cur_val:
- alist[pos] = alist[pos - gap]
- pos -= gap
- alist[pos] = cur_val
- def test_of_shell_sort():
- alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
- shell_sort(alist)
- print(alist)
- if __name__ == '__main__':
- test_of_shell_sort()
- 6. 归并排序
- 归并排序, 时间复杂度 O(nlogn).20 行.
- def merge_sort(alist):
- """
- 归并排序
- 1. 递归, 结束条件, 只有 1 个元素, return;
- 2. mid 中心, 左右两部分, 递归调用 merge_sort;
- 3. 遍历左右, 添加较小的值; 遍历其余部分;
- 4. 20 行
- :param alist:
- :return:
- """
- if len(alist) <2:
- return
- mid = len(alist) // 2
- left_half = alist[:mid]
- right_half = alist[mid:]
- merge_sort(left_half)
- merge_sort(right_half)
- i, j, k = 0, 0, 0
- while i < len(left_half) and j < len(right_half):
- if left_half[i] < right_half[j]:
- alist[k] = left_half[i]
- i += 1
- else:
- alist[k] = right_half[j]
- j += 1
- k += 1
- while i < len(left_half):
- alist[k:] = left_half[i:]
- while j < len(right_half):
- alist[k:] = right_half[i:]
- def test_of_merge_sort():
- alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
- merge_sort(alist)
- print(alist)
- if __name__ == '__main__':
- test_of_merge_sort()
- 7. 快速排序
- 快速排序, 时间复杂度 O(nlogn). 不需要额外空间 14 行, 需要额外空间 7 行.
- def quick_sort(alist, fst, lst):
- """
- 快速排序
- 1. 确定终止条件, 起始等于终止;
- 2. 起始 fst 和终止 lst 的位置, 枢轴的值 pivot;
- 3. 遍历 i 和 j,
- :param alist: 待排序列表
- :param fst: 起始 idx
- :param lst: 终止 idx
- :return: None
- """
- if fst>= lst:
- return
- i, j = fst, lst
- pivot = alist[fst]
- while i <= j:
- while alist[i] <pivot:
- i += 1
- while alist[j]> pivot:
- j -= 1
- if i <= j:
- alist[i], alist[j] = alist[j], alist[i]
- i, j = i + 1, j - 1
- quick_sort(alist, fst, j)
- quick_sort(alist, i, lst)
- def quick_sort_v2(alist):
- """
- 快速排序
- :param alist:
- :return:
- """
- if len(alist) <2:
- return alist
- pivot = alist[0]
- small = [i for i in alist if i < pivot]
- medium = [i for i in alist if i == pivot]
- large = [i for i in alist if i> pivot]
- return quick_sort_v2(small) + medium + quick_sort_v2(large)
- def test_of_quick_sort():
- alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
- # quick_sort(alist, 0, len(alist) - 1)
- # print(alist)
- alist = quick_sort_v2(alist)
- print(alist)
- if __name__ == '__main__':
- test_of_quick_sort()
OK, that's all! Enjoy it!
来源: https://juejin.im/post/5bc5b4136fb9a05d171d6e7b