常见的排序方法时间复杂度

### 常见排序算法的时间复杂度

#### 冒泡排序 (Bubble Sort)

对于冒泡排序而言，在不同情况下其时间复杂度有所差异。最好的情况下，当数组已经有序时，只需要一次遍历即可完成排序操作，此时时间复杂度为 O(n)；然而在最坏的情况下，即逆序排列的数据集上执行该算法，则需进行 n*(n-1)/2 次比较交换动作，因此最坏情况下的时间复杂度达到 O(n²)，而平均下来也是接近于这个数值[^1]。

#### 插入排序 (Insertion Sort)

插入排序同样具有较好的性能表现特别是在处理几乎已排序列表的时候可以实现线性的效率也就是 O(n)，不过一般情形下它的平均与最糟糕状况都维持着二次方级别 O(n²) 的计算量[^2]。

#### 选择排序 (Selection Sort)

无论输入序列的状态如何——无论是完全随机还是近乎有序的选择排序始终保持着固定的模式来寻找最小值并将其放置到正确位置这使得它在整个过程中保持恒定的 O(n²) 复杂度既不会更好也不会更差。

#### 快速排序 (Quick Sort)

作为一种分治法策略的应用实例快速排序展示了优秀的渐近行为：理想状态下每次划分都能均匀分割待处理区间从而获得对数级递归深度配合线性扫描最终形成整体上的 O(n log n) 效率。但是由于实际运行依赖具体数据分布如果总是选取极端元素作为枢纽那么可能会退化成平方级别的开销 O(n²)。

#### 归并排序 (Merge Sort)

通过不断拆解问题直至单个元素再逐步合并的方式归并排序能够保证稳定的 O(n log n) 性能不受初始顺序影响，并且此过程中的额外内存消耗相对固定大约相当于原始数组大小所以空间复杂度是 O(n)。

#### 堆排序 (Heap Sort)

利用二叉堆结构特性可以在原地调整内部存储进而达成高效排序目的。尽管构建最大/小顶堆本身涉及到了 O(n) 工作量但在后续反复提取根节点重建堆形的过程中累积起来依旧呈现出了总体 O(n log n) 的特征而且不需要额外分配大量连续区块故拥有较小的空间占用 O(1)。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, 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


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


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


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


def merge_sort(arr):
    if len(arr)>1:
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i=j=k=0
        
        while i<len(L)and j<len(R):
            if L[i]<R[j]:
                arr[k]=L[i]
                i+=1
            else:
                arr[k]=R[j]
                j+=1
            k+=1
            
        while i<len(L):
            arr[k]=L[i]
            i+=1
            k+=1
            
        while j<len(R):
            arr[k]=R[j]
            j+=1
            k+=1


def heapify(arr,n,i):
    largest=i 
    l=2*i+1  
    r=2*i+2  

    if l<n and arr[largest]<arr[l]:
        largest=l
    
    if r<n and arr[largest]<arr[r]:
        largest=r
    
    if largest!=i:
        arr[i],arr[largest]=arr[largest],arr[i]

        heapify(arr,n,largest)


def heap_sort(arr):
    n=len(arr)
    
    for i in range(n//2-1,-1,-1):
        heapify(arr,n,i)
        
    for i in range(n-1,0,-1):
        arr[i],arr[0]=arr[0],arr[i]
        heapify(arr,i,0)