LQB（1）-python-各种基础排序

前言

除了内置的快速排序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[j+1]:arr[j], arr[j+1] = arr[j+1], 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(i+1, 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[j+1] = arr[j]  # 后移元素j -= 1arr[j+1] = 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_size=5):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）可考虑插入排序。

• 需要稳定排序时选择归并排序。