如何做优秀的视频网站设计,惠州网站seo,wordpress 如何进入数据库,济宁营销型网站建设1️⃣ 冒泡排序#xff08;Bubble Sort#xff09;
基本思想
重复地比较相邻的两个元素#xff0c;如果顺序错误就交换它们。一趟冒泡结束后#xff0c;最大#xff08;或最小#xff09;的元素会“浮”到末尾。下一趟时可以少比较一次#xff0c;因为最后的元素已经排好…1️⃣ 冒泡排序Bubble Sort
基本思想
重复地比较相邻的两个元素如果顺序错误就交换它们。一趟冒泡结束后最大或最小的元素会“浮”到末尾。下一趟时可以少比较一次因为最后的元素已经排好。
过程示例升序
假设数组[5, 3, 8, 4, 2]
第一趟比较
(5, 3) → 交换 → [3, 5, 8, 4, 2](5, 8) → 不换 → [3, 5, 8, 4, 2](8, 4) → 交换 → [3, 5, 4, 8, 2](8, 2) → 交换 → [3, 5, 4, 2, 8] ✅ 最大的 8 已到末尾
第二趟比较不用管最后的 8
(3, 5) → 不换(5, 4) → 交换 → [3, 4, 5, 2, 8](5, 2) → 交换 → [3, 4, 2, 5, 8] ✅ 次大值 5 已到倒数第二位
… 直到全部有序。
时间复杂度
最坏情况O(n²)逆序最好情况O(n)已排序可加优化空间复杂度O(1)
Python 代码
def bubble_sort(arr):n len(arr)for i in range(n):swapped False # 优化如果一趟没交换说明已排序for j in range(0, n - i - 1):if arr[j] arr[j 1]:arr[j], arr[j 1] arr[j 1], arr[j]swapped Trueif not swapped:breakreturn arr# 示例
data [5, 3, 8, 4, 2]
print(bubble_sort(data))2️⃣ 选择排序Selection Sort
基本思想
每一趟从未排序部分选择最小或最大元素放到已排序部分的末尾。每趟交换次数固定为 1 次但比较次数较多。
工作过程示例升序
初始数组[5, 3, 8, 4, 2]
第一趟
在 [5, 3, 8, 4, 2] 中找到最小值 2交换 2 和第一个元素 → [2, 3, 8, 4, 5]
第二趟
在 [3, 8, 4, 5] 中最小值 3不动 → [2, 3, 8, 4, 5]
第三趟
在 [8, 4, 5] 中最小值 4交换 → [2, 3, 4, 8, 5]
第四趟
在 [8, 5] 中最小值 5交换 → [2, 3, 4, 5, 8]
时间复杂度
最坏情况O(n²)最好情况O(n²)比较次数固定空间复杂度O(1)
Python 代码
def selection_sort(arr):n len(arr)for i in range(n):min_idx ifor j in range(i 1, n):if arr[j] arr[min_idx]:min_idx jarr[i], arr[min_idx] arr[min_idx], arr[i]return arr# 示例
data [5, 3, 8, 4, 2]
print(selection_sort(data))3️⃣ 插入排序Insertion Sort
基本思想
将数组分为已排序区和未排序区。每次从未排序区取出一个元素插入到已排序区的合适位置。
工作过程示例升序
初始数组[5, 3, 8, 4, 2]
第一步i1
已排序区 [5]取 3插入到 5 前面 → [3, 5, 8, 4, 2]
第二步i2
已排序区 [3, 5]取 8放到末尾 → [3, 5, 8, 4, 2]
第三步i3
已排序区 [3, 5, 8]取 4插到 5 前面 → [3, 4, 5, 8, 2]
第四步i4
已排序区 [3, 4, 5, 8]取 2插到最前面 → [2, 3, 4, 5, 8]
时间复杂度
最坏情况O(n²)最好情况O(n)已排序空间复杂度O(1)对小规模数据或基本有序数据非常快
Python 代码
def insertion_sort(arr):for i in range(1, len(arr)):key arr[i] # 当前要插入的元素j i - 1while j 0 and arr[j] key:arr[j 1] arr[j] # 后移j - 1arr[j 1] keyreturn arr# 示例
data [5, 3, 8, 4, 2]
print(insertion_sort(data))对比总结算法最好时间最坏时间稳定性空间复杂度适用场景冒泡排序O(n)O(n²)稳定O(1)数据量小且大致有序选择排序O(n²)O(n²)不稳定O(1)数据量小对交换次数敏感插入排序O(n)O(n²)稳定O(1)数据基本有序小规模排序
