Python排序算法的时间复杂度分析

def bubble_sort(array):
    length = len(array)
    for i in range(length):
        for j in range(length-1-i):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return array

array = [8, 3, 9, 4, 6, 2]
print(bubble_sort(array))

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

array = [8, 3, 9, 4, 6, 2]
print(selection_sort(array))

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

array = [8, 3, 9, 4, 6, 2]
print(insertion_sort(array))

def shell_sort(array):
    length = len(array)
    gap = length // 2
    while gap > 0:
        for i in range(gap, length):
            j = i
            while j >= gap and array[j] < array[j-gap]:
                array[j], array[j-gap] = array[j-gap], array[j]
                j -= gap
        gap //= 2
    return array

array = [8, 3, 9, 4, 6, 2]
print(shell_sort(array))

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

def merge(left, right):
    result = []
    i, j = 0, 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

array = [8, 3, 9, 4, 6, 2]
print(merge_sort(array))

def quick_sort(array):
    if len(array) < 2:
        return array
    pivot = array[0]
    less = [x for x in array[1:] if x <= pivot]
    greater = [x for x in array[1:] if x > pivot]
    return quick_sort(less) + [pivot] + quick_sort(greater)

array = [8, 3, 9, 4, 6, 2]
print(quick_sort(array))