欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Python 排序 冒泡排序 希尔排序 快速排序 插入排序 选择排序 归并排序

程序员文章站 2022-05-12 16:55:38
...

排序

1 冒泡排序—-稳定

  • 最大的数像冒泡一样依次浮出
  • 紧挨着的两个数,两两相比,通过交换,大的永远排在后,依次循环,替换,最大的数就排在了最后面
  • 两个for循环嵌套,内部循环负责从左到右依次比对,外部循环负责比对循环的次数
  • 立旗优化,若循环一遍,没有更替,则已为正序排序,直接退出循环
  • 时间复杂度 最优:O(n),最坏O(n**2)
  • 最优 遍历一次发现没有任何需要交换的元素
def bubble_sort(alist):
    """冒泡排序"""
    n = len(alist)
    for j in range(1,n-1):
        # exchange_flag = False
        for i in range(n-j):
            if alist[i] > alist[i+1]:
                alist[i],alist[i+1] = alist[i+1],alist[i]
                exchange_flag = True
        # if not exchange_flag:
        #     break

2 选择排序—-不稳定

  • 立旗,给元素做标记,记为最小值,依次拿其他元素做对比,遇到把比它小的元素,更改标记,直至找到最小的元素
  • 按着列表排列顺序,依次更换
  • 外循环负责每次内循环开启时,最小值旗帜的开始位置
  • 内循环负责找出最小时,并排序
  • 时间复杂度:最优最坏均为O(n**2)
def selection_sort(alist):
    """选择排序"""
    n = len(alist) 
    for j in range(n):
        min_flag = j
        for i in range(j+1,n):
            if alist[i] < alist[min_flag]:
                min_flag = i
        alist[j],alist[min_flag] = alist[min_flag],alist[j]

3 插入排序—-稳定

  • 将序列分为两部分,一部分是有序的,一部分是无序的
  • 起始:将角标为0的元素认定为有序的,后面的认为是无序的
  • 将无序的元素与有序的元素,逐个对比,若无序元素大,则不变,
  • 若无序元素小,则与比对元素替换,并继续与角标小的有序元素逐个继续比对, 直至比对到无序元素为大
  • 两个for循环,内部循环负责依次往前比对,遇到比自己大的元素则替换
  • 外部循环负责每次内部循环开始的位置,从角标1到最后
  • 时间复杂度:最优O(n) 最坏O(n**2)
  • 最优:升序排列,序列已经处于升序状态
def insert_sort(alist):
    """插入排序"""
    n = len(alist)
    for j in range(1,n):
        for i in range(j,0,-1):
            if alist[i] < alist[i-1]:
                alist[i],alist[i-1] = alist[i-1],alist[i]
            else:
                break

4 希尔排序—-不稳定

  • 插入排序的优化版本,将无序的序列变得相对有序
  • 内部循环每次根据步长分组,每次循环的步长为上次的一半,直至最后一次按照插入排序进行
  • 原理是相对有序的序列在进行插入排序的时候break的机会增多,时间复杂度为nlogn~ n**2
  • 内部循环因为步长不同的时候均有循环,不确定循环次数,用while,用i<=gap控制循环结束
  • 时间复杂度:最优:以步长序列不同而不同 最坏:O(n**2)
  • 最坏:步长为1,即插入排序
def shell_sort(alist):
    """希尔排序"""
    n = len(alist)
    gap = n//2
    while gap > 0:
        for i in range(gap, n):
            while i >= gap and alist[i] < alist[i - gap]:
                alist[i], alist[i - gap] = alist[i - gap], alist[i]
                i -= gap
        gap //= 2

5 快速排序—-不稳定

  • 设立一个基准值,起始值为下标为0的数
  • 序列左边和序列最右边各有一个游标
  • 从右游标开始,和基准值做对比,如果比基准值大,则右游标向左移动,否则,将该值替换到左标记的位置
  • 替换之后,换左标记的位置开始右移比对,如果小于基准值,继续右移,否则,将该值替换到右标记的位置
  • 左右游标依次活动,直至相遇,相遇时,把把基准值赋给左游标的元素
  • 在相遇处的左右两边继续进行此项活动
  • 和归并排序相比因为不需要开辟额外空间,所以应用更多,置于稳定,看应用场景,如果需要稳定排序,则考虑归并排序
  • 时间复杂度 最优:O(nlogn),最坏O(n**2)
  • 每次排序时间复杂度O(n),一共执行了logn次
  • 最坏考虑的情况是,例如:每次设立基准值之后,右边只有大于它的数
def quick_sort(alist,start,end):
    """快速排序"""
    if start >= end:
        return
    left = start
    right = end
    base_value = alist[left]

    while left < right:
        while left < right and base_value <= alist[right]:
            right -= 1
        alist[left] = alist[right]
        while left < right and base_value > alist[left]:
            left += 1
        alist[right] = alist[left]

    alist[left] = base_value

    quick_sort(alist,start,left-1)
    quick_sort(alist,left+1,end)

归并排序—-稳定

  • 递归思想,自己调用自己进行拆分
  • 第一步:二步拆分,直至把所有的元素拆开为单个存在的列表
  • 第二步:循环,合并数组,逐步分组排序,两组直接进行比较列表
  • 新建列表,把元素按大小加入到新的列表中
  • 时间复杂度:最优最坏均为:O(nlogn)
  • 拆分为O(1),两两合并为O(n),两两合并共执行了logn次
  • 归并排序因为重新定义了一个列表,所以在空间上额外需要消耗一块内存
def merge_sort(alist):
    """归并排序"""
    n = len(alist)
    if n == 1:
        print(alist)
        return alist
    left,right = 0,0
    mid_flag = n // 2
    left_list = merge_sort(alist[:mid_flag])
    right_list = merge_sort(alist[mid_flag:])

    merge_sort_list = []
    lcount = len(left_list)
    rcount = len(right_list)

    while left < lcount and right < rcount:
        # 加上等号,是稳定的
        if left_list[left] <= right_list[right]:
            merge_sort_list.append(left_list[left])
            left += 1
        else:
            merge_sort_list.append(right_list[right])
            right += 1

    merge_sort_list += left_list[left:]
    merge_sort_list += right_list[right:]

    return merge_sort_list



if __name__ == '__main__':
    alist = [54,26,93,17,77,31,44,55,20]
    # bubble_sort(alist)
    # selection_sort(alist)
    # insert_sort(alist)
    # quick_sort(alist,0,len(alist)-1)
    # shell_sort(alist)
    # print(alist)
    print(merge_sort(alist))
"""
归并排序执行步骤
alist = [54,26,93,17,77,31,44,55,20]
n = 9
mid_flag = 4 取left[:4]
left_list = merge_sort([54,26,93,17])  # -1-这个函数体停在这句话,重新调用函数
    alist 变为 [54,26,93,17]
    n = 4
    mid_flag = 2
    left_list = merge_sort([54,26])  # -2-函数体停在这里,重新调用函数
        n = 2
        mid_flag = 1
        left_list = merge_sort([54])  # -3-函数体停在这里,重新调用函数
            n = 1
            return [54]  # -4- 函数体执行结束,-3-函数体获得返回值
            left_sort = [54]  # -3-函数体获得返回值,-3-可以继续往下执行
            right_list = merge_sort([26])
            return [26]
            right_list = [26]
            进入while循环 ,[54]和[26]进行拼接 return [26,54]  # -3-函数体执行结束,-2-函数体获得返回值
        left_list = [26,54] # -2-函数体获得返回值,-2-函数体继续执行
        right_list = merge_sort([93,17])  # -2-函数体停在这里,重新调用函数
            n = 2
            mid_flag = 1
            left_list = merge_sort([93])  # -2-1-函数体停在这里,重新调用函数
                n = 1
                return [93]  # -2-2-函数体结束 -2-1-获得返回值
                left_list = [93]  # -2-1-获得返回值, -2-1-继续执行
                right_list = merge_sort([17])  # -2-1-函数体停在这里,重新调用函数
                    n = 1
                    return [17]  # --函数体结束,-2-1- 函数获得返回值
                right_list = [17]  # -2-1- 函数获得返回值,继续执行合并,函数结束,-2-函数获得返回值
        right_list = [17,93]  # -2- 获得返回值,可以继续执行合并,-1-获得返回值
    left_list = [17,26,54,93]  # -1-获得返回值,可以继续执行函数体
    right_list = [77,31,44,55,20]
    ........

"""