美文网首页
常见算法python实现

常见算法python实现

作者: 邹霉霉 | 来源:发表于2018-04-19 09:12 被阅读0次

    1.冒泡排序,T(n) = O(n**2)

    # 冒泡排序,T(n) = O(n**2)
    def bubble_sort(li):
        print(li)
        for i in range(len(li)-1):  # i代表第几趟
            for j in range(len(li) - i - 1): # j代表每趟过程中的下标
                if li[j] > li[j + 1]:
                    li[j], li[j +1] = li[j + 1], li[j]
            print(li)
        return li
    
    
    # bubble_sort([9,8,7,6,5,4,3,2,1])
    

    2.选择排序,T(n) = O(n**2)

    # 选择排序
    def select_sort(li):
        for i in range(len(li)-1):
            min_index = i
            for j in range(i, len(li)):
                if li[j] < li[min_index]:
                    min_index = j
            li[i],li[min_index] = li[min_index], li[i]
        return li
    # print(select_sort([1,9,2,8,3,6,4,5,7]))
    

    3.插入排序,T(n) = O(n**2)

    # 插入排序,
    def insert_sort(li):
        for i in range(1, len(li)):  # i代表每次摸到的牌的下标
            tmp = li[i]
            j = i - 1   # j代表手里最后一张牌的下标
            while True:
                if j < 0 or tmp >= li[j]:
                    break
                li[j + 1] = li[j]
                j -= 1
            li[j + 1] = tmp
    
        return li
    

    4.快速排序,T(n) = O(nlogn)

    # 快速排序
    def quick_sort(li, left, right):
        if left < right:
            mid = partition(li, left, right)
            quick_sort(li, left,  mid-1)
            quick_sort(li, mid+1, right)
    
    
    def partition(data, left, right):
        tmp = data[left]
        while left < right:
            while left < right and data[right] >= tmp:
                right -= 1
            data[left] = data[right] # 第一次不满足条件时,right值固定
            while left < right and data[left] <= tmp:
                left += 1
            data[right] = data[left]
        data[left]=tmp
        return left
    
    print(quick_sort(li, 0, len(li)-1))
    print(li)
    

    5.堆排序,T(n) = O(nlogn)

    # 堆排序
    def sift(data, low, high):
        """
        调整函数
        data: 列表
        low:待调整的子树的根位置
        high:待调整的子树的最后一个节点的位置
        """
        i = low
        j = 2 * i + 1
        tmp = data[i]
        # i指向空位置
        while j<=high:      #领导已经撸到底了
            if j != high and data[j] < data[j+1]:
                j += 1
            #j指向数值大的孩子
            if tmp < data[j]:   #如果小领导比撸下来的大领导能力值大
                data[i] = data[j]
                i = j
                j = 2*i+1
            else:
                break       #撸下来的领导比候选的领导能力值大
        data[i] = tmp
    
    
    def heap_sort(data):
        n = len(data)
        # 建堆
        for i in range(n//2-1, -1, -1):
            sift(data, i,  n - 1)
        # 挨个出数
        for high in range(n - 1, -1, -1):
            data[0], data[high] = data[high], data[0]
            sift(data, 0, high - 1)
    

    6.归并排序,T(n) = O(nlogn)

    # 归并排序
    def merge(li, low, mid, high):
        i = low
        j = mid + 1
        ltmp = []
        while i <= mid and j <= high:
            if li[i] <= li[j]:
                ltmp.append(li[i])
                i += 1
            else: # li[i]>li[j]
                ltmp.append(li[j])
                j += 1
        while i <= mid:
            ltmp.append(li[i])
            i += 1
        while j <= high:
            ltmp.append(li[j])
            j += 1
        li[low:high+1]=ltmp
    
    
    def mergesort(li, low, high):
        if low < high:
            mid = (low + high) // 2
            mergesort(li, low, mid)
            mergesort(li, mid+1, high)
            merge(li, low, mid, high)
    
    

    7.希尔排序

    TODO...
    

    8.基数排序

    TODO

    相关文章

      网友评论

          本文标题:常见算法python实现

          本文链接:https://www.haomeiwen.com/subject/yhvikftx.html