【python数据结构算法篇】python算法

持续更新中。。。。
每个算法的工作原理是GPT拷贝来的，很标准的解析，，，，，但实现代码里面的注释是我根据经验自己总结的，可能不太标准，就大致凑合着看吧

0. 介绍

和数据结构一起总结，相当于双指针了，hhh

1. 查找算法（枚举）

1.1 顺序查找算法

没什么好说的，其实就是遍历，不配叫算法！哈哈哈

1.1.1 实现

def liner_search(li, item):for idx, val in enumerate(li):if item == val:return idxreturn "item is not match!"

1.2 二分查找算法

1.2.1 工作原理

1. 前提条件： 数组必须是已排序的，如果数组未排序，则必须先进行排序（排序本身也有时间复杂度）。

2. 初始边界： 设定两个指针，left 和 right，分别指向数组的起始和结束位置。

3. 迭代查找：

   1. 计算中间索引 mid = (left + right) // 2。
   2. 比较中间元素 arr[mid] 和要查找的值 target：
   3. 如果 arr[mid] 等于 target，则找到了目标值，返回 mid。
   4. 如果 arr[mid] 小于 target，则目标值在右半部分，调整 left = mid + 1。
   5. 如果 arr[mid] 大于 target，则目标值在左半部分，调整 right = mid - 1。
   6. 重复以上步骤，直到找到目标值或 left 超过 right（表示目标值不存在）。

4. 结束条件： 当 left 大于 right 时，表示查找结束，目标值未找到。

1.2.2 实现

def binary_search(li, val):# 定义左边界left = 0# 定义右边界right = len(li) - 1# 判断如果左边界大于右边界退出循环,并没有找到该值while left <= right:# 定义中间值mid  = (left+right) // 2# 如果中间值就是需查找的值，则找到并退出循环if li[mid] == val:return mid# 如果mid小于需查找的值val，则需查找的值在mid右边，左边和mid舍弃，将mid+1设置为左边界elif li[mid] < val:left = mid + 1# 如果mid大于val，则需要查找的值在mid左边，右边值和mid舍弃，将mid-1设置为右边界else:right = mid-1return "item is not match!"

2. 排序算法

排序算法多了去了，b站刷到过256种排序算法的比较，这里总结最常用的十种排序算法。当然值得一提的是，理论最强排序算法是：：：猴子算法！！🐒，最优时间复杂的o(0)（无论多大的数据，一步到位）!
基本上每一种基本算法都有它的优化变形算法，就连最基本的冒泡排序都有变形，不是牺牲空间换时间，就是牺牲时间换空间，这里就不总结了，太多了（其实是我不会）

2.1 冒泡排序算法

入门三人组算法NO.1
最简单的排序算法，通过重复地遍历要排序的元素，通过交换相邻的未按照顺序排列的元素，将较大的元素逐步“冒泡”到数组的末尾， 不够高效但简单啊！！
时间复杂度为o(n²)；空间复杂度为o(1)；最优时间复杂度为o(n)

2.1.1 工作原理

1. 遍历数组： 从数组的第一元素开始，逐个比较相邻的元素。
2. 交换顺序：
   1. 如果前面的元素大于后面的元素，则交换二者的位置。
   2. 如果前面的元素小于或等于后面的元素，则不进行操作。
3. 重复过程： 对整个数组进行多次遍历，直到没有发生交换，意味着数组已经排序。
4. 结束条件： 遍历完成后，如果没有元素需要交换，则数组已经排序完毕。

2.1.2 实现

def bubble(li):# 从第0号元素开始遍历，一直到n-1个元素for i in range(len(li)-1):# 设置标记flag = False# 内循环，循环遍历n-i-1次(n代表数组长度)for j in range(len(li)-i-1):# 判断后一个元素是否大于前一个元素if li[j] > li[j+1]:# 如果大于，则交换位置，否则不交换li[j], li[j+1] = li[j+1], li[j]# 如果执行过交换，则标记设为Trueflag  = True# 如果执行完一遍内循环后，没有需要交换的值，则已排序完成if not flag:breakreturn li

2.2 选择排序算法

入门三人组算法NO.2
每一轮从未排序的部分中选出最小（或最大）的元素，放到已排序部分的末尾，不够高效但也是简单啊！！
时间复杂度为o(n²)；空间复杂度为o(1)；最优时间复杂度为o(n²)

2.2.1 工作原理

1. 遍历未排序的部分： 找到未排序部分中最小（或最大）的元素。
2. 交换： 将找到的最小（或最大）元素与未排序部分的第一个元素交换。
3. 重复： 对未排序的部分重复步骤 1 和 2，直到所有元素都排序完成。

2.2.2 工作步骤

假设有一个数组 arr，其长度为 n。

1. 初始化: 从数组的第一个元素开始，将它视为当前的最小值，索引为 minIndex。
2. 比较: 从未排序部分的下一个元素开始，遍历到数组末尾，比较当前元素与当前最小元素（arr[minIndex]）。
3. 如果找到更小的元素，更新 minIndex。
4. 交换: 在遍历完成后，将当前最小元素与未排序部分的第一个元素进行交换。
5. 推进: 将已排序部分的长度增加 1，未排序部分的长度减少 1。
6. 重复: 重复步骤 1 至步骤 4，直到所有元素排完。

2.2.3 实现

def select_sort(li):# 遍历数组，现将第i个数视为最小值，用min_index指针指向最小值for i in range(len(li)):min_index = i# 内置循环，从第i+1个元素开始遍历 for j in range(i+1, len(i)):# 如果第j个元素小于假定的最小值，则将最小值指针指向jif li[j] < li[min_index]:min_index = j# 内循环结束后，如果最小值指针不是指向i了，则将i的值和指针指向的值互换if min_index != i:li[i], li[min_index] = li[min_index], li[i]return li

2.3 插入排序算法

入门三人组算法NO.3
将待排序的元素逐一插入到已排序的部分，直到所有元素都排序完成，不高效但直观
时间复杂度为o(n²)；空间复杂度为o(1)；最优时间复杂度为o(n)

2.3.1 工作原理

插入排序可以看作是把一个数组分为已排序部分和未排序部分，初始时已排序部分只有第一个元素。算法从第二个元素开始，依次将每个未排序的元素插入到已排序部分的正确位置。其基本步骤如下：

1. 初始化: 将第一个元素视为已排序部分。
2. 遍历未排序部分: 从数组的第二个元素开始，依次向后处理每个元素。
3. 插入: 将当前元素（未排序部分的元素）与已排序部分的元素进行比较，寻找合适的位置进行插入：
   从后往前比较，直到找到一个比当前元素小的位置，将当前元素插入到该位置。
4. 重复: 重复步骤 2 和 3，直到未排序部分所有元素都被插入到已排序部分。

2.3.2 实现

def insert_sort(li):# 直接将第一个元素视为已排序的部分，遍历从第二个元素开始之后的所有元素for i in range(1, len(i)):# 内置循环，从已排好序的第i个元素开始，从后往前进行遍历for j in range(i, 0, -1):# 如果第j个元素小于它前一个元素，则交换位置if li[j] < li[j-1]:li[j], li[j-1] = li[j-1], li[j]# 否则，跳出内循环else:breakreturn li

2.4 希尔排序算法

晋级四人组算法NO.1
基于插入排序的排序算法，属于不稳定排序。它通过将数据分为若干个子序列进行局部排序，从而提高整体的排序效率。希尔排序的核心思想是局部有序可以使得整体更有效地排序，因此它首先对间隔较大的元素进行排序，逐步减小间隔，最终实现全体元素有序
时间复杂度为o(n²)；空间复杂度为o(1)；最优时间复杂度为o(n)（其实平均时间复杂度应该算是o(n^1.5)）

2.4.1 工作原理

1. 选择一个增量序列： 初始选择一个增量（gap）值，通常可以选取数组长度的一半，然后依次减半，直到增量为 1。
2. 进行分组和局部排序： 对于每个增量，将数组按照当前增量分成若干个子序列，然后对每个子序列进行插入排序。
3. 缩小增量： 减小增量值，并重复步骤 2，直到增量为 1。
4. 最终排序： 当增量为 1 时，对整个数组进行一次插入排序，这时数组大体上已经是有序的，排序过程会比较快。

2.4.2 实现

def shell_sort(li):# 首先设置步长，增量值我就不设置1/2，我就要设置为n*3+1step = 1# 开启一个循环，按照n*3+1的公式往上寻找最大步长(如果列表长度为10，则step循环可以设置为1,1*3+1=4，4*3+1=13，由于步长13大于列表长度，而且4也已经大于len(li)/3，所以说不现实的，按此公式最大步长就为4)while step <= len(li)/3:step = step * 3 + 1# 再开启循环，如果步长小于等于0了，则退出循环while step > 0:# 就按插入排序方式，根据步长进行插入排序，直到退出循环# 将第一个元素设置为已排序元素，则下一个元素下标为step，就从step开始遍历for i in range(step, len(li)):# 内置循环，按照设置好的步长对已排序的元素进行反向遍历比较for j in range(i, 0, -step):# 如果j元素小于前一个元素(j-step元素)则交换if li[j] < li[j-step]:li[j], li[j-step] = li[j-step], li[j]# 否则退出内循环else:break# 循环步长整除3寻找下一个步长值，如果步长值还是大于等于0，则继续循环# 例如，step=4已经遍历完成，按照公式，下一个步长为1，公式就是每次除3取整即可step //= 3

如果记不住希尔排序原理，可以先了解插入排序，然后将所有插入排序中的1值替换为step，再加个循环即可

2.5 快速排序算法

晋级四人组算法NO.2
快速排序（Quick Sort）是一种高效的排序算法，由计算机科学家霍普克罗夫特（C.A.R. Hoare）在1960年提出。快速排序利用分治法（Divide and Conquer）的思想，将一个数组分为两个子数组（左右），然后递归地对这两个子数组进行排序。由于其分治性和平均时间复杂度的优势，快速排序在实际应用中被广泛使用
排序算法中一般使用到分治思想的，都很快！！
时间复杂度为o(nlog₂n)；空间复杂度为o(log₂n)；最优时间复杂度为o(nlog₂n)（因为用了递归，所以空间复杂度为log₂n）

2.5.1 工作原理

1. 选择基准（Pivot）：
   选择一个元素作为“基准”，通常可以选择数组的第一个元素、最后一个元素、或者更复杂的选择方法（如三数取中）。
2. 分区（Partition）：
   将数组调整为两个部分：
   1. 所有小于基准的元素放在基准的左边。
   2. 所有大于基准的元素放在基准的右边。
   3. 排序后，基准元素处于其最终位置。
3. 递归排序：
   对基准左侧和右侧的子数组分别执行快速排序，直到子数组的大小为 0 或 1。

2.5.2 实现

def quick_sort(li, start, end):# 判断开始和终止位置，如果开始位置比终止位置还大或等于，则退出循环if start < end:# 将开始值设置为基准值mid = li[start]# 设置左右指针分别指向起始和终止位置left = startright = end# 设置循环，如果左指针大于等于右指针(说明子数组大小为0,1，实现递推控制)，则退出循环while left < right:# 双循环实现将比基准值大的数放在右边，比基准值小的数放在左边# 左循环，外循环控制不了内循环，所以内循环中也要加一个左右指针判断while li[left] < mid and left < right:# 如果循环成立，则比mid小的值就在mid左边，值不需要动，左指针指向下一个值，继续判断left += 1# 如果循环不成立，则将值放到mid右边（和右指针的值进行调换，就放到右边去了），然后进入右循环li[left] = li[right]# 右循环，同样要加个左右指针判断while li[right] > mid and left < right:# 如果循环成立，则大值就在mid右边，值不需要动，右指针指向下一个值，继续判断right -= 1# 如果循环不成立，则将值放到mid左边（和左指针的值进行调换，就放到左边去了），然后再进入做循环li[right] = li[left]# 循环完毕后，则mid左侧都是比mid的值小的值，右侧都是比mid的值大的值# 则mid的值就为中间值，让左（右也行）指针的值设置为mid，进行二分，然后进入递归，对二分后的子列表再次进行上述操作，直到子列表的大小为 0 或 1，也就是start>=end，则排序完成li[left] = mid# 左侧递归quick_sort(li, start, mid-1)# 右侧递归quick_sort(li, mid+1, end)

2.6 归并排序算法

晋级四人组算法NO.3
高效的排序算法，采用“分治法”（Divide and Conquer）的思想，时间复杂度优于平均情况 O(n²) 的排序算法。特别对于大数据量的排序，归并排序具有较好的性能，被广泛应用于各种场景
和快排一样，排序算法中一般使用到分治思想的，都很快！！
时间复杂度为o(nlog₂n)；空间复杂度为o(n)；最优时间复杂度为o(nlog₂n)（因为需要使用外数组进行合并，所以空间复杂度为n）

2.6.1 工作原理

快排是先计算后递归，归并是先递归好，再计算，再合并。

1. 分解：
   将待排序的数组从中间分为两个子数组，递归地对两个子数组进行排序，直到每个子数组只包含一个元素。
2. 合并：
   将两个已经排好序的子数组合并成一个新的有序数组。合并的过程包括将两个数组的元素逐一比较，按顺序放入新数组中。

2.6.2 实现

def merge_sort(li):# 分解到子列表元素为1个即可退出合并if len(li) >= 1:# 采用二分法思想mid = len(li) // 2# 将大列表按mid二分成两个小的子列表left = li[:mid]right = li[mid:]# 分别再对两个子列表进行递归，直到拆分到最后子列表仅剩一个元素时left = merge_sort(left)right = merge_sort(right)# 定义一个外列表result = []# 定义两个指针i = 0j = 0# 实现拉链式(左右交替)向外列表中添加元素# 将单元素子列表进行拉链式合并while i < len(left) and j < len(right):# 判断如果左子列表中i元素小于右子列表j元素，则左端第i个元素先入列if left[i] < right[j]:result.append(left[i])# 左指针往后移动一位,，指向的第二个元素再次与右子列表的j元素比较i += 1# 否则，右子列表的第j个元素先入列else:result.append(right[j])# 右指针往后移动一位,指向的第二个元素再次与左子列表的i元素比较j += 1# 可能右子列表已经全部append，退出上一个循环，但左子列表中还有元素，单个子列表中的元素肯定是已经排好序的，所以直接遍历append即可while i < len(left):result.append(left[i])i += 1# 同上，左全部append，右剩余元素直接遍历append即可while j < len(right):result.append(right[j])j+=1return resultreturn li

2.7 堆排序算法

一定先了解树的概念，不然基于树排序的堆排序搞不懂！！！
晋级四人组算法NO.4
堆排序（Heap Sort）是一种基于堆（Heap）数据结构的比较排序算法，堆是一种完全二叉树，又分为大根堆和小根堆，根据树向下调整的原理进行建堆排序
学堆排序之前必须得掌握树的概念，这个参见数据结构里树
时间复杂度为o(nlog₂n)；空间复杂度为o(1)

2.7.1 工作原理

1. 构建大根（小根）堆： 从数组中构建大根（小根），使得数组的最大（最小）元素在根节点上。
2. 交换元素： 将最大（最小）元素（根节点）与数组中的最后一个元素交换，减少堆的大小。
3. 调整堆： 将被交换元素的根节点调整至正确的位置，重新形成大根（小根）堆。
4. 重复： 除去大根（小根）堆的根节点后，重复以上过程，直到堆的大小为 1。

2.7.2 实现

以大根堆为例

def sift(li, low, high):"""调整函数:param li: 列表:param low: 堆的根节点位置:param high: 堆的最后一个元素位置:return:"""# 设置指针指向根节点i = low# 设置指针指向根节点的左孩子节点j = 2* i + 1# 临时变量，存储根的值tmp = li[i]# 只有左孩子存在，就一直循环while j <= high:# 判断右孩子存在并且右孩子大于左孩子if j+1 <= high and li[j+1] > li[j]:# 则j指针指向右孩子j = j+1# 如果j指针的值大于根节点的值if li[j] > tmp:# 则j指针的值放上堆顶li[i] = li[j]# i指针指向下一层子树的根节点i = j# j指针 指向下一层子树根节点的孩子j = 2*i+1# 如果根节点更大，则退出循环elsebreak# 最后将根节点的值tmp放入它该在的位置li[i] = tmp# 堆排序函数
def heap_sort(li):n = len(li)# 从最后一个有孩子的节点开始，逆向遍历到根节点# 因为是完全二叉树，所以最后一个有孩子的节点计算公式为列表长度//2 - 1for i in range(n//2 -1, -1, -1):# 对树进行向下调整，建立大根堆# 建堆完成后进行出数# i指向当前堆的最后一个元素,逆向遍历列表for i in range(n-1, -1, -1):# 将根节点出数，放入列表的最后一位li[i], li[0] = li[0], li[i]# 对剩下的数再次建立大根堆(根节点出数后，剩下的数不一定可构成为大根堆，所以得再次建堆)# 因为根节点已排序，所以不再参与建堆，故high最后一个元素位置为i-1sift(li, 0, i-1)return li

2.8 计数排序算法

非比较排序算法NO.1
计数排序（Counting Sort）是一种非比较的排序算法适用于特定条件的有效排序。它的主要思路是统计每个待排序元素出现的次数，然后根据统计结果直接放入最终的有序数组中。计数排序的实现依赖于元素的范围，即假设待排序数组中的元素范围较小
条件严格，比如：如果有多位浮点数或特大值存在，直接歇菜。原理还是比较简单的，至少我认为堆排序思想是最复杂的
时间复杂度为o(n+k)；空间复杂度为o(k)（k=值的范围）

2.8.1 工作原理

1. 确定输入范围：
   找出待排序数组中的最大值和最小值，以便确定计数数组的大小。
2. 统计出现次数：
   创建一个计数数组 count，数组的索引对应于元素的值。遍历输入数组，统计每个元素出现的次数。
3. 累加计数：
   将计数数组中的每个元素作累加处理，使得 count[i] 表示小于或等于 i 的元素个数。这样可以确定每个元素在输出数组中的位置。
4. 构建输出数组：
   反向遍历输入数组，将每个元素放入输出数组的正确位置，并减少该位置在计数数组中的计数，确保稳定排序。
5. 复制回原数组：
   将最终的排序结果复制回原数组（如果需要）。

2.8.2 实现

def count_sort(li)# 查看最大值max_mum = max(li)# 建立统计列表，并设置列表占位符为0（其他也可）count = [0 for _ in range(max_mum)]# 循环遍历列表，如果列表元素与统计列表元素的索引一致，则对应索引位值+1for val in li:count[val] += 1# 为了节省空间，原表输出元素li.clear()# 遍历列表得到索引和值for idx, val in enumerate(count):# 按值循环，值为多少就append多少次该索引for i in range(val):li.append(idx)

2.9 桶排序算法

非比较排序算法NO.2
桶排序（Bucket Sort）是一种分布式排序算法，可以用于对数据进行排序，尤其适用于数值分布较均匀的情况。它的基本思想是将待排序的数据划分到若干个桶（Bucket）中，再对每个桶内的数据进行排序，最后将各个桶内的排序结果合并起来。
条件严格，比如：如果有多位浮点数或特大值存在，直接歇菜。原理还是比较简单的，至少我认为堆排序思想是最复杂的
时间复杂度为o(n + n/k log₂(n/k))；空间复杂度为o(n+k)；最优时间复杂度为o(n+k)（k=建通数量）

2.9.1 工作原理

1. 创建桶：
   确定待排序数组的最大值和最小值，根据这两个值将数据分布到若干个桶中。
   每个桶可以看作一个区间。
2. 分配数据到桶：
   遍历待排序数组，将每个元素放入适当的桶中。
   对于每一个元素，计算它属于哪个桶并放入相应的桶中。
3. 排序每个桶：
   对每个非空桶内部的数据进行排序。
   这里可以使用其他排序算法（如快速排序、归并排序或插入排序），具体选择取决于桶内元素的数量。
4. 合并桶：
   将所有非空的桶中排好序的元素连接起来，得到完全排序的数组。

2.9.2 实现

def bucket_sort(li, n=100, max_num=10000):"""桶的数量n和最大值max_num写死，可灵活修改，写函数里也可"""# 创建桶(100个)buckets = [[] for _ in range(n)]# 遍历数组for val in li:# 观察val适合放入几号桶# min判断：如果val=10000，则本应该放入100号桶(0号桶放0-99,1号桶放100-199...所以10000放到的是100号桶)，但桶的编号只有0-99，但就一个值，所以直接放入99号桶，怎么省怎么来i = min(val//(max_num//n), n-1)# 将val放入i号桶内buckets[i].append(val)# 逆向遍历分别对每个桶进行排序for j in range(len(buckets[i])-1, 0, -1):if buckets[i][j-1] > buckets[i][j]:buckets[i][j-1], buckets[i][j] = buckets[i][j], buckets[i][j-1]else:break# 创建新列表socket_sort = []# 将每个桶内元素添加到列表中for bucket in buckets:socket_sort.extend(bucket)return socket_sort

2.10 基数排序算法

非比较排序算法NO.3
基数排序（Radix Sort）是一种非比较的排序算法，它通过将数值分解为不同的位（digits）并逐位进行排序来实现整体排序。这种方法通常用于排序整数和字符串，尤其当数据范围较大时，基数排序可以在某些情况下优于传统的排序算法

时间复杂度为o(d(n + k))；空间复杂度为o(n+k)；最优时间复杂度为o(n+k)

2.10.1 工作原理

1. 确定最大位数：
   找出待排序数组中最大的数字，确定数字的位数。
2. 按位排序：
   从最低位（Least Significant Digit, LSD）开始，对每一位进行排序。可以使用稳定的排序算法（如计数排序）来实现对每一位的排序。
   重复这个过程，直到对所有位进行排序。
3. 合并结果：
   在每一位的排序完成后，较小的数字会自动排在前面，且相同的数字顺序不会被改变，保持稳定性。

2.10.2 实现

def radix_sort(li):# 找到列表中的最大数max_num = max(li)it = 0# 循环，看最大值的位数有几位，有几位就进行几次循环while 10**it <= max_num:# 建桶，只要建10个，分别对应每一位上的数字(0-9)buckets = [[] for _ in range(10)]# 遍历数组for val in li:# 确定该位数字是几，放入几号桶# val先对10**it取整，再对10取余，即可得到i = (val//10 ** it) % 10buckets[i].append(val)li.clear()# 遍历桶里数据append进列表中for bucket in buckets:li.extend(bucket)# 位数+1it +=1return li