快排代码

def quick_sort(li, start, end):
    if start >= end:
        return
    # 定义两个游标
    left = start
    right = end
    # 取0位置的数据，作为中间值
    mid = li[start]
    while left < right:
        # 让右边游标的下标往左移动，目的找到小于mid的数据，放到左边游标位置
        while left < right and li[right] >= mid:
            right -= 1
        li[left] = li[right]
        # 让左边游标的下标往右移动，目的找到大于mid的数据，放到右边游标位置
        while left < right and li[left] < mid:
            left += 1
        li[right] = li[left]
    # left=right,把mid放到此位置
    li[left] = mid
    # 对左右数据分别进行递归
    quick_sort(li, start, left-1)
    quick_sort(li, left+1, end)

if __name__ == '__main__':
    l = [2,5,1,4,3]
    # l = 2 [1,5,5,4,3]
    quick_sort(l,0,len(l)-1)
    print(l)

    # 稳定性：不稳定
    # 最坏时间复杂度：O(n^2)
    # 最优时间复杂度：O(nlogn)

归并代码

# [6,2,5,1,4,3]


def merge_sort(li):
    n = len(li)
    if n == 1:
        # print(li)
        return li

    # 根据列表长度获取中间位置
    mid = n//2
    # 把列表拆分成两半
    left = li[:mid]
    right = li[mid:]

    # print(left)
    # print(right)
    # 递归拆分左边
    left_res = merge_sort(left)
    # 递归拆分右边
    right_res = merge_sort(right)
    # res = left_res + right_res
    # 把下层方法返回的结果，组成有序
    res = merge(left_res, right_res)
    # print(res)
    return res


def merge(ll,rl):

    # 把两个有序序列，再组成有序
    # [2,5,6]   [1,3,4]
    l_index = 0
    r_index = 0
    # 定义临时结果列表
    res = []
    while l_index < len(ll) and r_index < len(rl):

        if ll[l_index] <= rl[r_index]:
            res.append(ll[l_index])
            l_index += 1
        else:
            res.append(rl[r_index])
            r_index += 1
    # 循环结束，肯定有一个列表的数据全部加入到结果
    res = res + ll[l_index:]
    res = res + rl[r_index:]
    return res


if __name__ == '__main__':
    l = [6,5,4,3,2,1]
    print(merge_sort(l))
    # l=[2, 5, 6]
    # r=[1, 3, 4,7,8]
    # print(merge(l,r))

    # 稳定性：稳定
    # 最坏时间复杂度：O(nlogn)
    # 最优时间复杂度：O(nlogn)

冒泡排序

def bubble_sort(li):

    n = len(li)
    # 让内部循环执行n-1次
    for j in range(n-1):  # 0 1 2 3

        count = 0
        # 定义游标，遍历列表，游标从0移动到倒数第二个位置
        for i in range(n-1-j):  # n-1 n-2 n-3
            # 比较当前游标位置和下一个位置的数据
            if li[i] > li[i+1]:
                li[i], li[i+1] = li[i+1], li[i]
                count += 1

        # 内部循环一次后，从来没有交换过，可以证明数据已经有序
        if count == 0:
            break

if __name__ == '__main__':
    l = [1,2,4,4,5]
    bubble_sort(l)
    print(l)

    # 稳定性：稳定
    # 最坏时间复杂度：O(n^2)
    # 最优时间复杂度：O(n)