选择排序
选择排序 基本概念 选择排序(Selection Sort)基本思想: 将数组分为两个区间:左侧为已排序区间,右侧为未排序区间。每趟从未排序区间中选择最小的元素,放到已排序区间的末尾。 算法步骤 假设数组长度为n,选择排序的算法步骤如下: 初始状态:已排序区间为空,未排序区间为[0,n−1][0,n−1][0,n−1]。 第i趟选择(i从1开始): 在未排序区间 [i−1,n−1][i−1,n−1][i−1,n−1]中找到最小元素的位置 minimin_imini。 将位置i−1的元素与位置minimin_imini的元素交换。 此时[0,i−1][0,i−1][0,i−1]为已排序区间,[i,n−1][i,n−1][i,n−1]为未排序区间。 重复步骤 2,直到未排序区间为空,排序完成。 内部实现: 1234567891011121314class Solution: def selectionSort(self,nums:[int])->[int]: n=len(nums) for i in range(n-1): min_i=i fo...
插入排序
插入排序 基本概念 插入排序(Insertion Sort)基本思想: 将数组分为有序区间和无序区间,每次从无序区间取出一个元素插入到有序区间的正确位置。 算法步骤 假设数组长度为 n,算法步骤如下: 初始化:有序区间为 [0,0][0,0][0,0],无序区间为 [1,n−1][1,n−1][1,n−1] 第i趟插入(i 从 11 到 n−1): 取出无序区间第一个元素 nums[i]nums[i]nums[i] 从右到左遍历有序区间,将大于 nums[i]nums[i]nums[i]的元素右移一位 找到合适位置后插入 nums[i]nums[i]nums[i] 有序区间扩展为 [0,i][0,i][0,i],无序区间变为[i+1,n−1][i+1,n−1][i+1,n−1] 内部实现: 123456789101112class Solution: def insertionSort(self,nums:[int])->[int]: for i in range(i,len(nums)): temp=nums[i] j=i while j&...
堆
堆 基本概念 堆(Heap):一种特殊的完全二叉树,具有以下性质之一: 大顶堆(Max Heap):任意节点值 ≥ 其子节点值 小顶堆(Min Heap):任意节点值 ≤ 其子节点值 数据结构的三要素 逻辑结构 树形结构 存储结构 顺序存储 父节点索引:(i - 1) // 2 左子节点:2*i + 1 右子节点:2*i + 2 数据的运算 费曼理解 堆就像是一个按优先级排队的队伍,队首总是优先级最高(最大或最小)的元素,你随时可以拿走它,也可以插入新人,队伍会自动调整顺序。 内部实现: python 创建空堆 123class MaxHeap: def _int_(self): self.max_heap=[] 访问堆顶元素 1234def peek(self)-> int: if not self.max_heap: return None return self.max_heap[0] 向堆种插入元素 向堆中插入元素需要两个步骤: 添加元素:将新元素添加到堆的末尾,保持完全二叉树的结构 上移调整:从新元素开始向上调整,...
堆排序
堆排序 基本概念 堆排序(Heap sort)基本思想: 利用堆的特性,将数组构建成大顶堆,然后重复取出堆顶元素(最大值)并调整堆结构,最终得到有序数组。 算法步骤 堆排序分为两个主要阶段: 第一阶段:构建初始大顶堆 将原始数组视为完全二叉树 从最后一个非叶子节点开始,自底向上进行下移调整 将数组转换为大顶堆 第二阶段:重复提取最大值 交换堆顶元素与当前末尾元素 堆长度减 1,末尾元素已排好序 对新的堆顶元素进行下移调整,恢复堆的性质 重复步骤 1∼3,直到堆的大小为 1 内部实现: 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748class MaxHeap: def __init__(self): self.max_heap = [] def __buildMaxHeap(self, nums: [int]): # 将数组元素复制到堆中 self.max...
冒泡排序
冒泡排序 基本概念 冒泡排序(Bubble Sort)基本思想: 通过相邻元素的比较与交换,将较大的元素逐步「冒泡」到数组末尾,较小的元素自然「下沉」到数组开头。 算法步骤 对于长度为 n 的数组,冒泡排序的步骤如下: 第1趟冒泡:对前n个元素依次比较相邻元素,将较大的元素向右交换,最终使最大值移动到数组末尾(第n个位置)。 比较第1个和第2个元素,如果前者大于后者则交换。 比较第 2 个和第 3 个元素,如果前者大于后者则交换。 以此类推,直到比较第 n−1 个和第 n 个元素。 完成后,最大元素已位于末尾。 第 2 趟冒泡:对前 n−1 个元素重复上述过程,将次大值移动到倒数第二个位置(第 n−1 个位置)。 比较第1个和第 2 个元素,如果前者大于后者则交换。 比较第 2 个和第 3 个元素,如果前者大于后者则交换。 以此类推,直到比较第 n−2 个和第 n−1 个元素。 完成后,次大元素已位于倒数第二位。 持续进行上述冒泡过程,每一趟比较的元素个数递减,直到某一趟未发生任何交换,说明数组已完全有序,排序结束。 内部实现: 1234567891011...
库存管理III-LeetCode
库存管理III 🎯 问题描述(来源于LeetCode) 描述: 仓库管理员以数组 stock 形式记录商品库存表,其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量,返回 顺序不限。 说明: 0 <= cnt <= stock.length <= 10000 0 <= stock[i] <= 10000 示例: 示例 1: 12输入:stock = [2,5,7,4], cnt = 1输出:[2] 示例 2: 12输入:stock = [0,2,3,6], cnt = 2输出:[0,2] 或 [2,0] 💻 解题思路 思路1:最小堆排序 思路1:代码实现 1234567891011121314151617181920212223242526272829303132class Solution: def maxHeap(self,nums:[int],i:int,heap_size:int): while 1: l_i=2*i+1 ...
数组种的第k个最大元素-LeetCode
数组种的第k个最大元素 🎯 问题描述(来源于LeetCode) 描述: 给定整数数组 nums 和整数 k,请返回数组中第 k个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 说明: 1 <= k <= nums.length <= 105 -104 <= nums[i] <= 104 示例: 示例 1: 12输入: [3,2,1,5,6,4], k = 2输出: 5 示例 2: 12输入:[3,2,3,1,2,4,5,5,6],k = 4输出: 4 💻 解题思路 思路1:堆排序 思路1:代码实现 1234567891011121314151617181920212223242526class Solution: def maxHeap(self,nums:[int],i:int,heap_size:int): while 1: l_i=2*i+1 r_...
链栈
链栈 基本概念 数据结构的三要素 逻辑结构 线性结构 存储结构 链式存储 数据的运算 费曼理解 12栈结构:头指针L → [栈顶节点] → [节点2] → ... → [栈底节点] → NULL 就像编绳结一样,一个节点一个结从右往左遍就得从左往右解 内部实现: 1234typedef struct Linknode{ ElemType data; struct Linknode *next;}*LiStack 复杂度分析: 初始化 1234bool InitStack(LiStack &L){ L= new Linknode; L->next=NULL;} 判断栈空 12345678bool isEmpty(LiStack &L){ if(L-next==NULL){ return true; } else{ return false; }} 入栈 1234567void Push(LiStack &L,Elem...
快速排序
快速排序 基本概念 快速排序(Quick Sort)基本思想: 采用分治策略,选择一个基准元素,将数组分为两部分:小于基准的元素放在左侧,大于基准的元素放在右侧。然后递归地对左右两部分进行排序,最终得到有序数组。 算法步骤 快速排序的核心是 分区操作,具体步骤如下: 选择基准:从数组中选择一个元素作为基准值(通常选择第一个元素) 分区操作: 使用双指针法,左指针从数组开始,右指针从数组末尾 右指针向左移动,找到第一个小于基准值的元素 左指针向右移动,找到第一个大于基准值的元素 交换这两个元素 重复上述过程,直到左右指针相遇 将基准值放到正确位置(左右指针相遇处) 递归排序:对基准值左右的两个子数组分别进行快速排序 内部实现: 12345678910111213141516171819202122232425import randomclass Solution: def randomPartition(self,nums:[int],low:int,high:int)->int: i=random.randint(low,high) nums[low]...
归并排序
归并排序 基本概念 归并排序(Merge Sort)基本思想: 利用分治法,将数组递归地一分为二,直至每个子数组只包含一个元素。随后,将这些有序子数组两两合并,最终得到一个整体有序的数组。 算法步骤 假设数组的元素个数为 n 个,则归并排序的算法步骤如下: 分解过程:递归地将当前数组平分为两部分,直到每个子数组只包含一个元素为止。 找到数组的中间位置 mid,将数组划分为左、右两个子数组left_nums 和 right_nums。 分别对 left_nums 和 right_numsr递归执行分解操作。 最终将原数组拆分为 n 个长度为 1 的有序子数组。 归并过程:从长度为 1 的有序子数组开始,逐步将相邻的有序子数组两两合并,最终合并为一个长度为 n 的有序数组。 新建数组 nums 用于存放合并后的有序结果。 设置两个指针 left_i 和 right_i,分别指向 left_nums 和 right_nums的起始位置。 比较两个指针所指元素,将较小者加入结果数组 numsnums,并将对应指针后移一位。 重复上述操作,直到某一指针到达对应子数组末尾。 ...










