如何使用更优的算法提高排序速度

Question

我采用冒泡法对一个数组进行排序，但我发现如果数组初始为反序时，其时间复杂度会很高，能否提供一种方法，使得我的排序算法在计算时间上变得稳定。

def bubble_sort(lst):

    n = len(lst)

    for i in range(n):

        for j in range(1, n - i):

            if lst[j - 1] > lst[j]:

                lst[j - 1], lst[j] = lst[j], lst[j - 1]

    return lst

Answer 1

直接进行递归会使得时间复杂度大大增加，故而我们从两边同时递归

def quick_sort(li):

    if len(li) <= 1:

        return li

    else:

        left = []

        right = []

        mid = li[0]

        for i in range(1,len(li)):

            if mid > li[i]:

                left.append(li[i])

            else:

                right.append(li[i])

        return quick_sort(left) + [mid] +quick_sort(right)

print(li1)

print(quick_sort(li1))