[数据结构与算法]python 选择排序 插入排序 冒泡排序 快速排序

↓↓↓选择排序↓↓↓

def select_sort(list_):
    """
        选择排序
        [4, 9, 3, 1, 2, 5, 8, 7]
        [1, 9, 3, 4, 2, 5, 8, 7]
        [1, 2, 3, 4, 9, 5, 8, 7]
        [1, 2, 3, 4, 5, 9, 8, 7]
        [1, 2, 3, 4, 5, 7, 8, 9]
    :param list_:
    :return:
    """
    count = 0

    for r in range(len(list_) - 1):
        min_index = r
        for c in range(r, len(list_)):
            count += 1
            if list_[min_index] > list_[c]:
                min_index = c
        if min_index != r:
            list_[r], list_[min_index] = list_[min_index], list_[r]
            print(list_)
    print('一共计算了%d次' % count)

↓↓↓插入排序↓↓↓

def insert_sort(list_):
    """
        插入排序
        [4, 9, 3, 1, 2, 5, 8, 7]
        [4, 9, 3, 1, 2, 5, 8, 7]
        [3, 4, 9, 1, 2, 5, 8, 7]
        [1, 3, 4, 9, 2, 5, 8, 7]
        [1, 2, 3, 4, 9, 5, 8, 7]
        [1, 2, 3, 4, 5, 9, 8, 7]
        [1, 2, 3, 4, 5, 8, 9, 7]
        [1, 2, 3, 4, 5, 7, 8, 9]
        [1, 2, 3, 4, 5, 7, 8, 9]
    :param list_:
    :return:
    """
    print(list_)
    for r in range(1,len(list_)):
        x = list_[r]
        c = r - 1
        while c >= 0 and list_[c] > x:
            list_[c + 1] = list_[c]
            c -= 1
        list_[c + 1] = x
        print(list_)

↓↓↓冒泡排序↓↓↓

def bubble_sort(list_):
    """
        冒泡排序
        [4, 9, 3, 1, 2, 5, 8, 7]
        [4, 3, 9, 1, 2, 5, 8, 7]
        [4, 3, 1, 9, 2, 5, 8, 7]
        [4, 3, 1, 2, 9, 5, 8, 7]
        [4, 3, 1, 2, 5, 9, 8, 7]
        [4, 3, 1, 2, 5, 8, 9, 7]
        [4, 3, 1, 2, 5, 8, 7, 9]
        [3, 4, 1, 2, 5, 8, 7, 9]
        [3, 1, 4, 2, 5, 8, 7, 9]
        [3, 1, 2, 4, 5, 8, 7, 9]
        [3, 1, 2, 4, 5, 7, 8, 9]
        [1, 3, 2, 4, 5, 7, 8, 9]
        [1, 2, 3, 4, 5, 7, 8, 9]
    :param list_:
    :return:
    """
    count = 0
    n = len(list_)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            count += 1
            if list_[j] > list_[j + 1]:
                list_[j], list_[j + 1] = list_[j + 1], list_[j]
                print(list_)
    print('一共计算了%d次' % count)

↓↓↓快速排序↓↓↓

def quick_sort(list_, low, high):
    """
        快速排序
        第一次
        [2, 1, 3, 4, 9, 5, 8, 7]
        第二次
        [1, 2, 3, 4, 9, 5, 8, 7]
        第三次
        [1, 2, 3, 4, 7, 5, 8, 9]
        第四次
        [1, 2, 3, 4, 5, 7, 8, 9]
    :param list_:
    :return:
    """

    # 完成一轮交换
    def sub_sort(list_, low, high):
        """

        :param list:
        :param low: 第一个元素索引
        :param high: 最后一个元素索引
        :return:
        """
        # 选定基准
        x = list_[low]
        # low 向右 high向左
        while low < high:
            # 右边的数 向左
            while list_[high] >= x and high > low:
                high -= 1
            list_[low] = list_[high]
            # print(list_)
            # 左边的数向右
            while list_[low] < x and low < high:
                low += 1
            list_[high] = list_[low]
            # print(list_)
        list_[low] = x
        print(list_)
        return low

    if low < high:
        print('第一次')
        key = sub_sort(list_, low, high)
        quick_sort(list_, low, key - 1)
        quick_sort(list_, key + 1, high)