❤❤算法基础&递归&查找&十大排序算法，献给快要开学的你❤❤

❤❤算法基础&递归&查找&十大排序算法，献给快要开学的你❤❤

算法入门

文章目录

​​修改最大递归次数​​​​一、时间复杂度和空间复杂度​​​​二、递归和汉诺塔​​​​三、查找​​

​​3.1线性查找​​​​3.2二分查找​​

​​四、排序​​

​​4.1LowB三人组​​

​​4.1.1冒泡排序O(n2)​​​​4.1.2选择排序O(n2)​​​​4.1.3插入排序O(n2)​​

​​4.2NB三人组​​

​​4.2.1快速排序O(nlogn) 最坏O(n2)​​​​4.2.2堆排序O(nlogn)​​

​​4.2.2.1内置模块​​​​4.2.2.2topk问题：小根堆​​

​​4.2.3归并排序O(nlogn)​​​​4.2.4NB三人组小结​​

​​4.3常用六大排序总结​​​​4.4其余排序​​

​​4.4.1希尔排序​​​​4.4.2计数排序​​​​4.4.3桶排序​​​​4.4.4基数排序​​

修改最大递归次数

import syssys.setrecursionlimit(100000)

计算机一秒大概执行107次python内部的排序sorted使用的是基于归并排序和插入排序的改良

一、时间复杂度和空间复杂度

时间复杂度：循环折半 O(logn)

二、递归和汉诺塔

递归两大要素：

终止条件调用自身

def hanoi(n, a, b, c): ''' 汉诺塔 :param n: 盘子数 :param a: 盘子一开始所在柱子 :param b: 中间柱子 :param c: 目标柱子 :return: ''' if n == 0: return # 将n-1个盘子从a移动到b，需要经过c hanoi(n - 1, a, c, b) # 将最后一个盘子从a移动到c print(f"盘子从{a}移动到{c}") # 将n-1个盘子从b移动到c，需要经过a hanoi(n - 1, b, a, c)

三、查找

3.1线性查找

def linear_search(lis, val): ''' 该方法同python内置的列表查找元素方法：index（无则报错） :param lis: 所要查询的列表 :param val: 所要查询的数据 :return: - 查到则返回该元素的索引（下标） - 未查到返回None ''' for index, v in enumerate(lis): if v == val: return

3.2二分查找

def binary_search(lis, val): ''' 二分查找: :param lis: 所要查询的列表 :param val: 所要查询的数据 :return: - 查到返回该元素的索引（下标） - 未查到返回None ''' left = 0 right = len(lis) - 1 while left <= right: mid = left + right // 2 if lis[mid] == val: return mid elif lis[mid] > val: # 所要查找的元素在mid左侧 right = mid - 1 else: # 所要查找的元素在mid右侧 left = mid + 1

递归实现

def binary_search(lis, val): ''' 二分查找: :param lis: 所要查询的列表 :param val: 所要查询的数据 :return: - 查到返回该元素的索引（下标） - 未查到返回None ''' n = len(lis) if n > 0: mid = n // 2 if lis[mid] == val: return mid elif lis[mid] < val: return binary_search(lis[mid + 1:], val) else: return binary_search(lis[:mid], val)

四、排序

默认升序

4.1LowB三人组

4.1.1冒泡排序O(n2)

def bubble_sort(lis): ''' 冒泡排序：需要遍历n-1趟，n为列表长度 :param lis: 所要排序的列表 :return: 返回排序好的列表 ''' # 第n趟,从0开始，每进行一趟，有序区元素增加一个，无序区元素减少一个 n = len(lis) for i in range(n - 1): flag = False # 记录当前趟是否有元素变动 for j in range(n - i - 1): if lis[j] > lis[j + 1]: lis[j], lis[j + 1] = lis[j + 1], lis[j] flag = True if not flag: return

4.1.2选择排序O(n2)

def select_sort(lis): ''' 选择排序：选择最小的元素放入列表最左侧 :param lis:所要排序的列表 :return: 排序好的列表 ''' n = len(lis) # 需要进行n-1趟 for i in range(n - 1): min_loc = i # 每一趟遍历无序区 for j in range(i + 1, n): if lis[j] < lis[min_loc]: min_loc = j # 将找到的元素和有序区对应的位置进行交换 if min_loc != i: lis[i], lis[min_loc] = lis[min_loc], lis[i] return

4.1.3插入排序O(n2)

4.2NB三人组

def insert_sort(lis): ''' 插入排序：摸牌，从无序区中拿走元素放入有序区合适位置 :param lis: 所要排序的列表 :return: 排序好的列表 ''' for i in range(1, len(lis)): # i为无序区的牌的下标 temp = lis[i] # 当前摸到的无序区牌 j = i - 1 # 有序区的最后一个元素的下标 # 寻找无序区插入的位置 while j >= 0 and temp < lis[j]: # 如果无序区的元素小于有序区最后一个元素， # 1.将大于无序区元素的元素往右移动 # 2.继续往左遍历无序区，直到找到一个比无序区值大的，放到它右边 # 比无序区牌大的值往后移动 lis[j + 1] = lis[j] # 继续往左遍历 j -= 1 lis[j + 1] = temp print(lis) return

4.2.1快速排序O(nlogn) 最坏O(n2)

最坏情况

1）数组已经是正序（same order）排过序的。2）数组已经是倒序排过序的。3）所有的元素都相同（1、2的特殊情况）

def partition(lis, left, right): ''' 用于确定快速排序中间元素：从右边找一个比当前元素小的，从右边找一个比当前元素大的 :param lis: 操作的列表 :param left: 列表的左下标 :param right: 列表的又下标 :return: 返回当前元素的中间位置下标 ''' temp = lis[left] # 列表第一个元素 while left < right: # 从列表的右边找一个比当前元素小的 while left < right and temp <= lis[right]: right -= 1 # 将该元素放到列表第一个元素位置 lis[left] = lis[right] # 从列表的左边找一个比当前元素大的 while left < right and temp >= lis[left]: left += 1 # 将该元素放到最右边 lis[right] = lis[left] print(lis) mid = left lis[mid] = temp return middef quick_sort(lis, left, right): ''' 快速排序，递归 终止条件是无序区至少有俩元素，否则递归终止 :param lis: 所要进行排序的列表 :param left: 列表的左下标 :param right: 列表的右下标 :return: 排好序的列表 ''' if left < right: # 至少有俩元素，只有一个元素或者无元素的时候不需要排序，即递归结束 mid = partition(lis, left, right) quick_sort(lis, left, mid - 1) # 左边进行快速排序 quick_sort(lis, mid + 1, right) # 右边进行快速排序 return

4.2.2堆排序O(nlogn)

def sift(data, low, high): ''' 向下调整 基于大根堆 :param lis: 要调整的堆 :param low: 堆列表的左下标 :param high: 堆列表的右下标 :return: ''' i = low # 当前元素指针 j = 2 * i + 1 # 当前元素左孩子指针 temp = data[i] # 堆顶元素 # 遍历整个堆 while j <= high: # 当前元素有孩子，非叶子节点 if j + 1 <= high and data[j] < data[j + 1]: # 右孩子存在且大于左孩子 j += 1 if temp < data[j]: # 堆顶元素小于孩子元素,将孩子元素写入当前位置，继续往下遍历 data[i] = data[j] i = j # 更新当前元素指针，往下看一层 j = 2 * i + 1 # 更新左孩子指针 else: break # 当整个遍历结束时，也就是i到了叶子节点，将堆顶元素写入当前位置 data[i] = tempdef heap_sort(data): ''' 堆排序：建立堆（农村包围城市）、挨个出数 :param data: 要进行排序的堆 :return: 返回排序好的堆 ''' n = len(data) # 建立堆 for i in range(n // 2 - 1, -1, -1): # i表示的是每一个小堆的堆顶下标，农村包围城市，反向遍历 sift(data, i, n - 1) # 挨个出数 for i in range(n - 1, -1, -1): # i 表示的是队尾的位置 # 将堆顶元素放到最后一个位置，将堆尾元素放上来 data[0], data[i] = data[i], data[0] sift(data, 0, i - 1) return

4.2.2.1内置模块

# 堆排序内置模块import heapqlis = [1, 5, 7, 1, 2, 3, 7, 8]# 建堆，小根堆heapq.heapify(lis)# 挨个出数for i in range(len(lis) - 1): print(heapq.heappop(lis))'''1123577'''

4.2.2.2topk问题：小根堆

def sift2(data, low, high): ''' 向下调整 基于小根堆 :param lis: 要调整的堆 :param low: 堆列表的左下标 :param high: 堆列表的右下标 :return: ''' i = low # 当前元素指针 j = 2 * i + 1 # 当前元素左孩子指针 temp = data[i] # 堆顶元素 # 遍历整个堆 while j <= high: # 当前元素有孩子，非叶子节点 if j + 1 <= high and data[j] > data[j + 1]: # 右孩子存在且小于左孩子 j += 1 if temp > data[j]: # 堆顶元素大于孩子元素,将孩子元素写入当前位置，继续往下遍历 data[i] = data[j] i = j # 更新当前元素指针，往下看一层 j = 2 * i + 1 # 更新左孩子指针 else: break # 当整个遍历结束时，也就是i到了叶子节点，将堆顶元素写入当前位置 data[i] = temp# topk问题def topk(lis, k): li = lis[:k] n = len(lis) # 建立小根堆 for i in range(n // 2 - 1, -1, -1): sift2(li, 0, k - 1) print(li) for i in range(k, n): if lis[i] > li[0]: li[0] = lis[i] sift2(li, 0, k - 1) print(li) # 挨个出数 for i in range(k - 1, -1, -1): li[0], li[i] = li[i], li[0] sift2(li, 0, i - 1) return lilis = [1, 5, 7, 1, 2, 3, 7, 8]print(topk(lis, 3))

4.2.3归并排序O(nlogn)

def merge(lis, low, mid, high): ''' 归并 合并两个分别有序的列表 :param lis: 所要合并的列表 :param low: 列表的左下标 :param mid: 列表的中间下标 :param high: 列表的右下标 ''' i = low j = mid + 1 ltmp = [] while i <= mid and j <= high: if lis[i] <= lis[j]: ltmp.append(lis[i]) i += 1 else: ltmp.append(lis[j]) j += 1 while i <= mid: ltmp.append(lis[i]) i += 1 while j <= high: ltmp.append(lis[j]) j += 1 lis[low:high + 1] = ltmpdef merge_sort(lis, low, high): ''' 归并排序 将列表拆分 + 递归 至少有两个元素 少于2个元素递归终止 :param lis: 所要排序的列表 :param low: 列表的左下标 :param high: 列表的右下标 ''' if low < high: mid = (low + high) // 2 # 让左右列表有序 merge_sort(lis, low, mid) merge_sort(lis, mid + 1, high) merge(lis, low, mid, high)

4.2.4NB三人组小结

4.3常用六大排序总结

4.4其余排序

4.4.1希尔排序

希尔排序的时间复杂度讨论⽐较复杂，并且和选取的gap序列有关。

def shell_sort(lis): ''' 希尔排序 分组插入 在插入排序的基础上增加分组 :param lis: 要排序的列表 :return: 排序好的列表 ''' gap = len(lis) // 2 # 每隔gap取一个元素 while gap > 0: for i in range(gap, len(lis)): # i 是无序区元素下标 # 插入排序 temp = lis[i] # 当前位置元素 j = i - gap # j是有序区最后一个元素的下标 # 寻找合适的插入位置 while j >= 0 and temp < lis[j]: lis[j + gap] = lis[j] # 有序区元素往右移动 j -= gap lis[j + gap] = temp gap //= 2 return

4.4.2计数排序

def count_sort(lis, max_num): ''' 计数排序 :param lis: 所要排序的列表 :param max_num: 列表中最大的数 :return: 排序好的列表 ''' count = [0 for _ in range(max_num + 1)] for val in lis: count[val] += 1 # 列表存储的是每个元素的个数 i = 0 for ind, val in enumerate(count): for j in range(val): lis[i] = ind i += 1 return

4.4.3桶排序

def bucket_sort(lis, n=100, max_num=10000): ''' 桶排序 :param lis: 所要排序的列表 :param n: 桶的个数 :param max_num: 列表中最大的元素 :return: 返回排序好的列表 ''' # 创建桶 buckets = [[] for i in range(n)] # 将元素放入相应的桶中 for val in lis: i = min((val // (max_num // n)), n - 1) # i表示放入几号桶 buckets[i].append(val) # 将元素放入桶 # 保持桶内的顺序 for j in range(len(buckets[i]) - 1, 0, -1): if buckets[i][j] < buckets[i][j - 1]: # 判断当前元素和前一个元素的大小 buckets[i][j], buckets[i][j - 1] = buckets[i][j - 1], buckets[i][j] else: break sort_lis = [] for buc in buckets: sort_lis.extend(buc) return

4.4.4基数排序

操作演示：最大数是94 两位，所以需要进行两次装桶和分桶第一步根据个位装桶32 13 94 17 52 93 54第二步分桶32 52 13 93 94 54 17 # 先按照个位排第三步十位装桶13 32 52 93 17 54 94第四步分桶13 17 32 52 54 93 94 # 再按照十分位排

def radix_sort(lis): ''' 基数排序 以最大数的位数为基准，从个位开始根据每一位，放入0-9不同的桶中，后分桶,重复这个过程 :param lis: 所要排序的列表 :return: 返回要排序好的列表 ''' # 获取最大值，根据最大值的位数，判断要装桶的次数 max_num = max(lis) n = len(str(int(max_num))) # n是最大数的位数 for i in range(n): buckets = [[] for _ in range(10)] for val in lis: dight = val // (10 ** i) % 10 # 依次取个位、十位。。。 buckets[dight].append(val) # 分桶 lis.clear() for buc in buckets: lis.extend(buc) return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。