如何用自己网站做大电商,搭建个网站,订票网站开发公司,wordpress内容新窗口打开前言
除了内置的快速排序sort()#xff0c;python也可以实现冒泡排序、选择排序、插入排序、快速排序、归并排序和桶排序。 一、冒泡排序 (Bubble Sort)
基础代码
def bubble_sort(arr):n len(arr)for i in range(n):swapped False # 优化#xff1a;若本轮无交换则提前…前言
除了内置的快速排序sort()python也可以实现冒泡排序、选择排序、插入排序、快速排序、归并排序和桶排序。 一、冒泡排序 (Bubble Sort)
基础代码
def bubble_sort(arr):n len(arr)for i in range(n):swapped False # 优化若本轮无交换则提前终止for j in range(n-i-1):if arr[j] arr[j1]:arr[j], arr[j1] arr[j1], arr[j]swapped Trueif not swapped:breakreturn arr
核心知识点 原理相邻元素两两比较将较大元素逐渐冒泡到右侧。每次循环都选出本循环最大的排后面 时间复杂度 最优O(n)已有序时 最差O(n²) 稳定性稳定相等元素不交换 适用场景小规模数据或教学演示 二、选择排序 (Selection Sort)
基础代码
def selection_sort(arr):n len(arr)for i in range(n):min_idx i # 记录最小元素索引for j in range(i1, n):if arr[j] arr[min_idx]:min_idx jarr[i], arr[min_idx] arr[min_idx], arr[i] # 交换位置return arr
核心知识点 原理每次从未排序部分选择最小元素与未排序部分的起始位置交换。 时间复杂度始终为 O(n²) 稳定性不稳定交换可能破坏顺序 适用场景简单实现但效率低一般仅用于教学 三、插入排序 (Insertion Sort)
基础代码
def insertion_sort(arr):for i in range(1, len(arr)):key arr[i] # 当前待插入元素j i-1while j 0 and key arr[j]:arr[j1] arr[j] # 后移元素j - 1arr[j1] key # 插入正确位置return arr
核心知识点 原理将未排序元素逐个插入已排序序列的正确位置。 时间复杂度 最优O(n)已有序时 最差O(n²) 稳定性稳定 适用场景小规模数据或近乎有序的数据 四、快速排序 (Quick Sort)
基础代码
def quick_sort(arr):if len(arr) 1:return arrpivot arr[len(arr)//2] # 选择中间元素为基准值left [x for x in arr if x pivot]middle [x for x in arr if x pivot]right [x for x in arr if x pivot]return quick_sort(left) middle quick_sort(right)
核心知识点 原理分治法 递归选择一个基准值将数组分为三部分小于、等于、大于基准值。 时间复杂度 平均O(n log n) 最差O(n²)当基准值选择不当时 稳定性不稳定 优化点三数取中法选择基准值、尾递归优化 适用场景大规模随机数据实际应用最广泛的排序算法 五、归并排序 (Merge Sort)
基础代码
def merge_sort(arr):if len(arr) 1:return arrmid len(arr) // 2left merge_sort(arr[:mid])right merge_sort(arr[mid:])return merge(left, right)def merge(left, right):result []i j 0while i len(left) and j len(right):if left[i] right[j]:result.append(left[i])i 1else:result.append(right[j])j 1result.extend(left[i:])result.extend(right[j:])return result
核心知识点 原理分治法将数组递归拆分为两半排序后合并。 时间复杂度始终 O(n log n) 空间复杂度O(n)合并时需要额外空间 稳定性稳定 适用场景需要稳定排序且内存充足时如数据库排序 六、桶排序 (Bucket Sort)
基础代码
def bucket_sort(arr, bucket_size5):if len(arr) 0:return arrmin_val, max_val min(arr), max(arr)bucket_count (max_val - min_val) // bucket_size 1buckets [[] for _ in range(bucket_count)]for num in arr:buckets[(num - min_val) // bucket_size].append(num)result []for bucket in buckets:result.extend(sorted(bucket)) # 每个桶使用其他排序算法return result
核心知识点 原理将数据分到有限数量的桶中每个桶单独排序后合并。 时间复杂度 平均O(n k)k为桶数量 最差O(n²)所有元素集中在一个桶时 稳定性取决于桶内排序算法的稳定性 适用场景数据分布均匀且范围已知如年龄排序 对比
算法时间复杂度平均稳定性空间复杂度适用场景冒泡排序O(n²)稳定O(1)教学演示选择排序O(n²)不稳定O(1)简单实现插入排序O(n²)稳定O(1)小规模或近乎有序数据快速排序O(n log n)不稳定O(log n)大规模随机数据归并排序O(n log n)稳定O(n)需要稳定排序且内存充足桶排序O(n k)稳定O(n k)数据分布均匀且范围已知
使用 优先选择快速排序Python内置的 sorted() 使用了 Timsort 算法结合了归并排序和插入排序。 对小规模数据如 n 100可考虑插入排序。 需要稳定排序时选择归并排序。
