数据结构排序算法时间复杂度

各种排序算法的时间复杂度比较
选择排序
选择排序是一种简单直观的排序方法，在每次迭代过程中从未排序部分选出最小（或最大）的一个元素，将其放到已排序序列的最后。该算法具有平方时间复杂度 (O(n^2))，适用于小型数组或作为教学工具来介绍基本排序原理[^1]。
冒泡排序
冒泡排序通过重复遍历要排序列表的方式工作，依次比较相邻两个元素并交换顺序不对者；此过程持续到整个队列有序为止。同样拥有(O(n^2))级别的平均与最差情况下运行效率，不过对于几乎已经排好序的数据集可以达到接近线性的表现即最好情况为(O(n))[^4]。
插入排序
插入排序构建最终排序阵列的方法是从左至右逐步处理未排序项，并将每一项放置于当前已知有序子集中恰当位置上完成增量式增长。它也具备较好的局部优化能力以及较低的空间占用率(O(1))，然而总体而言仍需面对(O(n^2))数量级的操作次数限制。
快速排序
作为一种分治法策略实现高效内省排列机制——快速排序能够在线性对数时间内完成大部分实例的任务解决((O(n\log{}n)))，尽管存在极端条件下退化成二次方程级别运算量的风险((O(n^2)))[^3]。值得注意的是，由于递归调用栈的存在使得额外内存消耗大约相当于输入规模大小取自然对数值的程度[(O(\log{}n))]。
归并排序
基于相同的思想框架下运作—即将待整理集合拆分为若干独立小组件分别治理后再合并起来形成全局秩序—归并与前者相比更加稳定可靠且不会轻易恶化性能指标，始终维持着稳定的(O(n\log{}n))时间开销不变的同时却牺牲了一定量存储资源用于辅助操作【具体来说就是需要额外分配等同原始数据长度的工作区】从而达到了空间复杂度(O(n))的效果。
def merge_sort(arr):
if len(arr) <= 1:
return arr

mid = len(arr) // 2
left_half = merge_sort(arr[:mid])
right_half = merge_sort(arr[mid:])

sorted_arr = []
while left_half and right_half:
if left_half[0] < right_half[0]:
sorted_arr.append(left_half.pop(0))
else:
sorted_arr.append(right_half.pop(0))

# Append any remaining elements from either half.
sorted_arr.extend(left_half or right_half)

return sorted_arr
登录后复制