【排序算法】典型排序算法和python 实现

以下是排序算法的分类及经典Python实现，包含时间复杂度、空间复杂度与稳定性说明：

一、比较类排序（通过元素间比较决定顺序）

1. 交换排序

1. 冒泡排序
   时间复杂度：O(n²)（最优O(n)已优化）
   空间复杂度：O(1)
   稳定性：稳定

   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 = True
           if not swapped: break  # 提前终止优化
       return arr
   

2. 快速排序
   时间复杂度：平均O(n log n)，最差O(n²)
   空间复杂度：O(log n)（递归栈）
   稳定性：不稳定

   def quick_sort(arr):
       if len(arr) <= 1:
           return arr
       pivot = 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)
   

2. 插入排序

1. 直接插入排序
   时间复杂度：O(n²)（最优O(n)）
   空间复杂度：O(1)
   稳定性：稳定

   def insertion_sort(arr):
       for i in range(1, len(arr)):
           key = arr[i]
           j = i - 1
           while j >= 0 and key < arr[j]:
               arr[j+1] = arr[j]
               j -= 1
           arr[j+1] = key
       return arr
   

3. 选择排序

1. 简单选择排序
   时间复杂度：O(n²)
   空间复杂度：O(1)
   稳定性：不稳定

   def selection_sort(arr):
       for i in range(len(arr)):
           min_idx = i
           for j in range(i+1, len(arr)):
               if arr[j] < arr[min_idx]:
                   min_idx = j
           arr[i], arr[min_idx] = arr[min_idx], arr[i]
       return arr
   

4. 归并排序

时间复杂度：O(n log n)
空间复杂度：O(n)
稳定性：稳定

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    res = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    res.extend(left[i:] or right[j:])
    return res

二、非比较类排序（利用数值特征避免元素间比较）

1. 计数排序

时间复杂度：O(n + k)（k为数据范围）
空间复杂度：O(n + k)
稳定性：稳定（反向填充时）
适用场景：整数且范围较小

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    res = []
    for i in range(len(count)):
        res.extend([i] * count[i])
    return res

2. 基数排序

时间复杂度：O(nk)（k为最大位数）
空间复杂度：O(n + k)
稳定性：稳定

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        buckets = [[] for _ in range(10)]
        for num in arr:
            buckets[(num // exp) % 10].append(num)
        arr = [num for bucket in buckets for num in bucket]
        exp *= 10
    return arr

3. 桶排序

时间复杂度：平均O(n + k)，最差O(n²)
空间复杂度：O(n + k)
适用场景：均匀分布的数据

def bucket_sort(arr, bucket_size=5):
    min_val, max_val = min(arr), max(arr)
    bucket_count = (max_val - min_val) // bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]
    for num in arr:
        idx = (num - min_val) // bucket_size
        buckets[idx].append(num)
    res = []
    for bucket in buckets:
        res.extend(sorted(bucket))
    return res

三、总结对比

根据数据规模与类型选择合适算法：小数据用简单排序（如插入），大数据优先选O(n log n)算法，特定场景使用非比较排序。