python数据结构与算法:

快排:最优复杂度 O(n*logn) 最坏时间复杂度O(n^2)平均时间复杂度n^(1.3)

 python数据结构与算法:

归并排序:最优/平均/最坏  时间复杂度均O(nlogn),但是内存占用为list大小的两倍,算法稳定 

 

############################## p5  排序 ###################################
def bubble_sort(alist):
    """顺序表实现bubble"""
    n=len(alist)
    for j in range(0,n-1):#遍历次数,没遍历一次 遍历长度-1 遍历j次 -j
        count = 0
        for i in range(0,n-1-j):#一次循环找到最大值,并且移动到最后位置  主体
            if alist[i]>alist[i+1]:
               alist[i],alist[i+1]=alist[i+1],alist[i]
               count+=1
        if 0 == count:
            return #####count 优化  不交换数字 不增加计数

def choose_sort(alist):
    """选择排序:找到最小的数字,放到最前面"""
    min = 0
    n = len(alist)
    for j in range(0,n-2):
        min = j
        for i in range(j+1,n):
            if alist[min]>alist[i]:
                min = i
        alist[j],alist[min] = alist[min],alist[j]

def insert_sort(alist):
    """插入排序,从右边去除一个数 ,房子啊最左边 在最左边排序,不断地从右边获取后面的数字"""
    n = len(alist)
    #从右边的无序序列中取出多少个元素执行这样的过程
    for j in range(1,n):
        #内层循环的起始值
        i = j
        #执行从右边的无序序列中去除第一个元素,即i位置的元素,插入到正确的位置
        while(i>0): #for i in range(i,0,-1)
            if alist[i] < alist[i-1]:
                alist[i], alist[i-1] = alist[i-1], alist[i]
                i -= 1
            else:
                break

def shell_sort(alist):
    """"希尔排序 不稳定 O(n^2) 分而治之 p5.7 -p5.8"""
    n = len(alist)
    gap = n//2  # python取整 双斜线
    while gap >= 1:#该循环将gap 变换到1 之前
    #插入算法与普通插入算法一样
        for j in range(gap,n):
            #j = [gap,gap+1,gap+2,.....,n ]
            i = j
            while(i>0):   ###除了间隔 gap 和插入算法一摸一样
                if alist[i] < alist[i-gap]:#
                    alist[i],alist[i-gap] = alist[i-gap],alist[i]
                    i -= gap
                else:
                    break
        gap //= 2

def quick_sort(alist, first, last):
    """"#快速排序  递归嵌套 最优时间复杂度nlgn"""
    if first >= last:
        return

    low = first
    high = last
    mid_value = alist[first]

    while low < high:
        while low < high and alist[high] >= mid_value: #high左移
            high -= 1
        alist[low] = alist[high]

        while low < high and alist[low] < mid_value:  # low右移
            low += 1
        alist[high] = alist[low]
    # 从循环退出时  low = high
    alist[low] = mid_value

    quick_sort(alist,first,low-1)  #对low左边的列表执行快排
    quick_sort(alist,low+1,last)   #对low右边的列表执行快排

def merge_sort(alist):
    """有额外开销 需要两倍的存储空间"""
    n = len(alist)
    if n<= 1:
        return alist
    mid = n//2
    ###拆分的过程部分代码
    left_li = merge_sort(alist[:mid])
    right_li = merge_sort(alist[mid:])

    ## 合并的部分代码 merge(left,right)
    left_pointer, right_pointer = 0, 0
    result = []

    ## 调整内部顺序
    while left_pointer < len(left_li) and right_pointer < len(right_li):
        if left_li[left_pointer] <= right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer += 1
        else:
            result.append(right_li[right_pointer])
            right_pointer += 1

    #####合并切片
    result += left_li[left_pointer:]
    result += right_li[right_pointer:]
    return result



if __name__ == "__main__":
    li = [54, 26, 2, 4, 5, 100, 102]
    print(li)
    # quick_sort(li, 0, len(li)-1)
    result_li = merge_sort(li)
    print(result_li)

    """
    merge_sort=[54, 26, 2, 4, 5, 100, 102]
    left_li = [54, 26, 2, 4]  right_li=
    left_li = [54, 26]  right_li = [2, 4] 
    left_li = [54]  right_li = [26]
    左边一半完成分割,开始进行排序操作
    执行 if n<= 1: list长度为1 ,返回自身  left_li = [54] 
        right_li = merge_sort(alist[mid:]) = merge_sort(【54,26】[mid=1:])=[26]
        right_li = [26]
            [54,26] 进行主循环   返回[2,4] 开始 执行 ## 调整内部顺序
               
    """

 

python数据结构与算法:python数据结构与算法: Darlingqiang 发布了75 篇原创文章 · 获赞 105 · 访问量 16万+ 私信 关注
上一篇:python-插入排序


下一篇:数据结构01——数组