常见排序算法性能对比

排序算法是计算机科学中将一个数据集合按照特定顺序如升序或降序重新排列的算法。根据是否通过比较元素来决定次序主要分为比较排序和非比较排序两大类 。常见排序算法对比下表对几种主流排序算法的核心特性进行了对比 算法名称平均时间复杂度最坏时间复杂度空间复杂度是否稳定核心思想冒泡排序O(n²)O(n²)O(1)稳定重复遍历依次比较相邻元素将最大/小元素“冒泡”到末尾。选择排序O(n²)O(n²)O(1)不稳定每次从未排序部分选择最小或最大元素放到已排序序列的末尾。插入排序O(n²)O(n²)O(1)稳定构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。希尔排序O(n¹·³)O(n²)O(1)不稳定插入排序的改进通过将数组按增量分组对每组进行插入排序逐步缩小增量至1。归并排序O(n log n)O(n log n)O(n)稳定分治法。将数组递归地分成两半分别排序然后将两个有序子数组合并成一个有序数组 。快速排序O(n log n)O(n²)O(log n)不稳定分治法。选取一个基准将数组分为小于基准和大于基准的两部分递归地对这两部分排序。堆排序O(n log n)O(n log n)O(1)不稳定利用堆一种完全二叉树数据结构将数组构建成大顶堆然后重复将堆顶元素最大与末尾交换并调整堆。计数排序O(n k)O(n k)O(n k)稳定非比较排序。适用于数据范围k不大的整数。统计每个值的出现次数然后按顺序输出。基数排序O(d * (n k))O(d * (n k))O(n k)稳定非比较排序。按位个位、十位...进行稳定排序如计数排序从低位到高位。算法原理与代码实现1. 冒泡排序每一轮遍历比较相邻元素如果顺序错误就交换这样每一轮都会将当前未排序部分的最大值“冒泡”到正确位置 。def bubble_sort(arr): n len(arr) for i in range(n - 1): # 进行 n-1 轮比较 swapped False for j in range(n - 1 - i): # 每轮比较的范围逐渐缩小 if arr[j] arr[j 1]: # 如果顺序错误则交换 arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: # 如果一轮没有交换说明已有序可提前结束 break return arr # 示例 arr [64, 34, 25, 12, 22, 11, 90] print(bubble_sort(arr)) # 输出: [11, 12, 22, 25, 34, 64, 90]2. 选择排序算法在未排序序列中找到最小元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小元素放到已排序序列的末尾以此类推 。def selection_sort(arr): n len(arr) for i in range(n - 1): # 进行 n-1 轮选择 min_idx i # 假设当前位置为最小值索引 for j in range(i 1, n): # 在未排序部分寻找更小的值 if arr[j] arr[min_idx]: min_idx j arr[i], arr[min_idx] arr[min_idx], arr[i] # 将找到的最小值与当前位置交换 return arr # 示例 arr [64, 25, 12, 22, 11] print(selection_sort(arr)) # 输出: [11, 12, 22, 25, 64]3. 插入排序将数组视为已排序和未排序两部分。初始时已排序部分只包含第一个元素。然后依次将未排序部分的元素插入到已排序部分的正确位置 。def insertion_sort(arr): n len(arr) for i in range(1, n): # 从第二个元素开始视为待插入元素 key arr[i] # 当前待插入的元素 j i - 1 # 将比 key 大的元素向后移动一位为 key 腾出位置 while j 0 and key arr[j]: arr[j 1] arr[j] j - 1 arr[j 1] key # 将 key 插入到正确位置 return arr # 示例 arr [12, 11, 13, 5, 6] print(insertion_sort(arr)) # 输出: [5, 6, 11, 12, 13]4. 归并排序采用分治法将数组递归地分成两半直到每个子数组只有一个元素自然有序然后将这些有序子数组合并起来 。def merge_sort(arr): if len(arr) 1: return arr # 1. 分解找到中间点将数组分成两半 mid len(arr) // 2 left_half arr[:mid] right_half arr[mid:] # 2. 解决递归地对左右两半进行排序 left_sorted merge_sort(left_half) right_sorted merge_sort(right_half) # 3. 合并将两个有序数组合并成一个 return merge(left_sorted, right_sorted) def merge(left, right): result [] i j 0 # 比较两个数组的头部将较小的放入结果数组 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 # 将剩余元素追加到结果数组 result.extend(left[i:]) result.extend(right[j:]) return result # 示例 arr [38, 27, 43, 3, 9, 82, 10] print(merge_sort(arr)) # 输出: [3, 9, 10, 27, 38, 43, 82]5. 快速排序选择一个元素作为“基准”将数组重新排列所有比基准小的放在基准前面比基准大的放在后面。然后递归地对基准前后的子数组进行快速排序 。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) # 示例 arr [10, 7, 8, 9, 1, 5] print(quick_sort(arr)) # 输出: [1, 5, 7, 8, 9, 10]特殊排序算法Stalin Sort这是一种非标准的、带有讽刺意味的“高效”算法。其核心思想是遍历数组只保留那些不破坏非递减顺序的元素而直接“移除”忽略任何比前一个保留元素小的元素从而实现“排序” 。def stalin_sort(arr): if not arr: return [] result [arr[0]] # 总是保留第一个元素 max_so_far arr[0] for i in range(1, len(arr)): if arr[i] max_so_far: # 只有当前元素不小于当前最大值时才保留 result.append(arr[i]) max_so_far arr[i] # 否则该元素被“移除”忽略 return result # 示例 arr [1, 2, 5, 3, 5, 7, 4, 9] print(stalin_sort(arr)) # 输出: [1, 2, 5, 5, 7, 9] # 注意原数组中的 3 和 4 被移除了结果序列是非递减的但已不是原数组的完整集合。算法选择与适用场景小规模或基本有序数据插入排序简单高效是许多高级算法如TimSort在小规模数据上的 fallback 选择 。通用且高效的比较排序快速排序在平均情况下性能极佳是许多语言标准库的默认排序实现。归并排序稳定且时间复杂度稳定为 O(n log n)常用于需要稳定排序或链表排序的场景 。原地排序且对空间有严格要求堆排序能保证最坏情况下的 O(n log n) 时间复杂度且只需要常数额外空间适用于内存受限环境 。非比较排序当数据是有限范围内的整数时计数排序和基数排序可以在 O(n) 时间内完成排序效率远超比较排序 。教学与理解冒泡排序和选择排序因其思路直观常被用于算法入门教学但在实际应用中因其 O(n²) 的时间复杂度而较少使用 。参考来源pythonsort函数时间复杂度_合并排序算法——时间复杂度详解和python代码实现排序算法详解选择排序算法详解含Python实现Java数据结构与算法_05 时间复杂度常用排序算法 冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、基数排序Java 四大基础排序算法详解冒泡、选择、插入与希尔排序Stalin Sort完全指南从原理到实现手把手教你掌握这个高效排序算法