【Python 算法零基础 4.排序 ② 冒泡排序】
从未排序序列开始，初始时整个数组都是未排序的。：遍历未排序部分的所有元素，找到其中的最小值。使用变量min_idx记录最小值的索引，初始时假设当前未排序部分的第一个元素是最小的。将找到的最小值与未排序部分的第一个元素交换位置。此时，未排序部分的第一个元素成为已排序序列的一部分。：缩小未排序部分的范围（从下一个元素开始），重复寻找最小值并交换的过程，直到整个数组排序完成。
目录
我走的很慢
从不是优秀的人
但是没关系
我很少停下
脆弱会给我新力量
—— 25.5.19
选择排序回顾
① 遍历数组：从索引 0 到 n-1（n 为数组长度）遍历数组。
② 每轮确定最小值：假设当前索引 i 为最小值索引 min_index。从 i+1 到 n-1 遍历，若找到更小元素，则更新 min_index。
③ 交换元素：若 min_index ≠ i，则交换 arr[i] 与 arr[min_index]。
'''
① 遍历数组：从索引 0 到 n-1（n 为数组长度）。
② 每轮确定最小值：假设当前索引 i 为最小值索引 min_index。从 i+1 到 n-1 遍历，若找到更小元素，则更新 min_index。
③ 交换元素：若 min_index ≠ i，则交换 arr[i] 与 arr[min_index]。
'''
def selectionSort(arr: List[int]):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
if min_index != i:
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr一、引言
冒泡排序（Bubble Sort）是一种简单的排序算法，通过多次比较和交换相邻的元素，将列表（数组）中的元素按照升序或降序排列
二、算法思想
冒泡排序的基本思想：每次遍历数组，比较相邻的两个元素，如果它们的顺序错误，就将它们交换，直到数组中的所有元素都被遍历过
具体的算法步骤如下：
① 遍历数组的第一个元素到最后一个元素。
② 对每一个元素，与其后一个元素进行比较。
③ 如果顺序错误，就将它们交换。
④ 重复上述步骤，直到数组中的所有元素都被遍历过至少一次。
三、时间复杂度和空间复杂度
1.时间复杂度
我们假设【比较】和【交换】的时间复杂度为O(1)
【冒泡排序】中有两个嵌套循环
外循环正好运行n - 1次迭代。但内部循环运行变得越来越短:
当i = 0，内层循环n - 1次【比较】操作。
当i = 1，内层循环n - 2次【比较】操作。
当i = 2，内层循环n - 3次【比较】操作。
当i = n - 2，内层循环1次【比较】操作。
当i = n - 1，内层循环0次【比较】操作。
因此，总「比较」次数如下：(n - 1) + (n - 2) + ... + 1 + 0 = n (n - 1) / 2，总的时间复杂度为：O(n ^ 2)
2.空间复杂度
由于算法在执行过程中，只有【交换】变量时候采用了临时变量的方式，而其它没有采用任何的额外空间，所以空间复杂度为O(1)。
四、冒泡排序的优缺点
1.算法的优点
① 简单易懂：冒泡排序的算法思想非常简单，容易理解和实现。
② 稳定排序：冒泡排序是一种稳定的排序算法，即在排序过程中不会改变相同元素的相对顺序。
2.算法的缺点
① 效率较低：由于需要进行多次比较和交换，冒泡排序在处理大规模数据时效率较低。
② 排序速度慢：对于大型数组，冒泡排序的时间复杂度较高，导致排序速度较慢。
五、实战练习
88. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组
nums1和nums2，另有两个整数m和n，分别表示nums1和nums2中的元素数目。请你 合并
nums2到nums1中，使合并后的数组同样按 非递减顺序 排列。注意：最终，合并后数组不应由函数返回，而是存储在数组
nums1中。为了应对这种情况，nums1的初始长度为m + n，其中前m个元素表示应合并的元素，后n个元素为0，应忽略。nums2的长度为n。示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1] 解释：需要合并 [1] 和 [] 。 合并结果是 [1] 。示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1 输出：[1] 解释：需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。提示：
nums1.length == m + nnums2.length == n0 <= m, n <= 2001 <= m + n <= 200-109 <= nums1[i], nums2[j] <= 109
算法与思路
① 合并数组
将 nums2 的前 n 个元素依次复制到 nums1 的后 n 个位置（从索引 m 开始）。
② 冒泡排序
使用两层循环对合并后的 nums1 进行升序排序：
外层循环遍历每个元素（索引 i 从 0 到 mn-1）。
内层循环比较 i 之后的所有元素（索引 j 从 i+1 到 mn-1）。
若发现 nums1[i] > nums1[j]，则交换两者位置。
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
for i in range(n):
nums1[m + i] = nums2[i]
mn = len(nums1)
for i in range(mn):
for j in range(mn - i -1):
if nums1[j] > nums1[j + 1]:
nums1[j], nums1[j + 1] = nums1[j + 1], nums1[j] 
2148. 元素计数
给你一个整数数组
nums，统计并返回在nums中同时至少具有一个严格较小元素和一个严格较大元素的元素数目。示例 1：
输入：nums = [11,7,2,15] 输出：2 解释：元素 7 ：严格较小元素是元素 2 ，严格较大元素是元素 11 。 元素 11 ：严格较小元素是元素 7 ，严格较大元素是元素 15 。 总计有 2 个元素都满足在 nums 中同时存在一个严格较小元素和一个严格较大元素。示例 2：
输入：nums = [-3,3,3,90] 输出：2 解释：元素 3 ：严格较小元素是元素 -3 ，严格较大元素是元素 90 。 由于有两个元素的值为 3 ，总计有 2 个元素都满足在 nums 中同时存在一个严格较小元素和一个严格较大元素。提示：
1 <= nums.length <= 100-105 <= nums[i] <= 105
算法与思路
① 排序
调用 bubbleSort 对数组进行升序排序。
② 初始化计数器
count = 0。
③ 遍历数组
对于每个元素 x，检查其是否不等于数组的第一个元素（最小值）和最后一个元素（最大值）。若是，则 count += 1。
④ 返回结果
最终计数器的值。
class Solution:
def bubbleSort(self, nums:List[int]):
n = len(nums)
for i in range(n):
for j in range(n - i - 1):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
def countElements(self, nums: List[int]) -> int:
self.bubbleSort(nums)
count = 0
for x in nums:
if x != nums[0] and x != nums[-1]:
count += 1
return count
1046. 最后一块石头的重量
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为
x和y，且x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎；- 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回
0。示例：
输入：[2,7,4,1,8,1] 输出：1 解释： 先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]， 再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]， 接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]， 最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。提示：
1 <= stones.length <= 301 <= stones[i] <= 1000
算法与思路
① 冒泡排序
每轮固定一个位置：通过外层循环 i 控制当前处理的位置，从 0 到 n-1。
比较后续所有元素：内层循环 j 从 i+1 开始，将 nums[i] 与后续所有元素比较。
交换较大值：若 nums[i] > nums[j]，则交换两者，确保 i 位置的元素是当前未排序部分的最小值。
② 石头碰撞模拟
初始化：获取石头数组长度 n，作为循环终止条件。
循环条件：当 n > 1 时，持续处理（确保至少有两块石头可碰撞）。
排序：每次循环调用 bubbleSort 对数组升序排序，使最重的石头位于末尾。
碰撞操作：取出最重的两块石头 stones[-1] 和 stones[-2]，计算差值 v。
更新数组：
移除碰撞的石头：通过两次 pop() 移除末尾两个元素，n 减 2。
添加新石头：若 v != 0（两块石头重量不同）或 n == 0（碰撞后无剩余石头），将 v 加入数组，n 加 1。
返回结果：循环结束后，若 n == 1，返回剩余石头 stones[0]
class Solution:
def bubble_sort(arr):
"""
冒泡排序的标准实现
"""
n = len(arr)
# 遍历所有数组元素
for i in range(n):
# 最后i个元素已经就位，无需再比较
for j in range(0, n-i-1):
# 遍历数组从0到n-i-1
# 交换元素如果当前元素大于下一个元素
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
def lastStoneWeight(self, stones: List[int]) -> int:
n = len(stones)
while n > 1:
self.bubbleSort(stones)
v = stones[-1] - stones[-2]
n -= 2
stones.pop()
stones.pop()
if v != 0 or n == 0:
stones.append(v)
n += 1
return stones[0]
GitCode 天启AI是一款由 GitCode 团队打造的智能助手，基于先进的LLM（大语言模型）与多智能体 Agent 技术构建，致力于为用户提供高效、智能、多模态的创作与开发支持。它不仅支持自然语言对话，还具备处理文件、生成 PPT、撰写分析报告、开发 Web 应用等多项能力，真正做到“一句话，让 Al帮你完成复杂任务”。
更多推荐
23
0- 0
已为社区贡献9条内容
所有评论(0)