排序算法

冒泡排序

时间复杂度：O(n^2)

def bubble_sort_2(_list):
    pass_num = len(_list) - 1
    while pass_num > 0:
        for i in range(pass_num):
            if _list[i] > _list[i+1]:
                temp = _list[i]
                _list[i] = _list[i+1]
                _list[i+1] = temp

        pass_num = pass_num -1

代码优化

def bubble_sort(_list):
    # for循环替代while循环
    for pass_num in range(len(_list)-1, 0, -1):
        for i in range(pass_num):
            if _list[i] > _list[i+1]:
                # 交换操作简写
                _list[i], _list[i+1] = _list[i+1], _list[i]

逻辑优化：短冒泡

def short_bubble_sort(_list):
    exchanges = True
    pass_num = len(_list) - 1
    while pass_num > 0 and exchanges:
        exchanges = False
        # 如果在一轮遍历中没有发生元素交换，则可以确定列表已经有序，将不继续做没有意义的循环
        for i in range(pass_num):
            if _list[i] > _list[i+1]:
                exchanges = True
                _list[i], _list[i+1] = _list[i+1], _list[i]

        pass_num = pass_num -1

选择排序

时间复杂度：O(n^2)

相对冒泡排序，减少了交换次数

def selection_sort(_list):
    for fill_slot in range(len(_list)-1, 0, -1):
        # 找出最大数的位置
        position_of_max = 0
        for location in range(1, fills_lot+1):
            if _list[location] > _list[position_of_max]:
                position_of_max = location
        # 把找出来的最大数与最前面的数置换位置
        _list[fill_slot], _list[position_of_max] = _list[position_of_max], _list[fill_slot]

插入排序

时间复杂度：O(n^2)

交换操作相当于三次赋值操作，移动操作相当于一次赋值操作，所以交换操作的处理时间大约是移动操作的3倍

于是用移动操作来替代交换操作，可以提高处理速度

希尔排序

时间复杂度：O(n) ~ O(n^2)

归并排序

时间复杂度：O(n^logn)

快速排序

---

最后更新: 2023-04-02