创新路
我们一直在努力

[Learn.Practice.Discovery]Vol.2 烧脑不停,折腾不止 时间复杂度&空间复杂度&几种排序算法的Python实现

  这2个概念之前一直困扰着我,一直都是懵懵懂懂。感觉好像知道,但是又说不出个所以然。下面分享下自己针对这2个概念所了解收集的一些东西,希望对有兴趣的小伙伴能有所帮助。

算法复杂度.png

  说到事件复杂度和空间复杂度不得不提他们总的概念,算法复杂度。算法复杂度,即算法在编写成可执行程序后,运行时所需要的资源,资源包括时间资源和内存资源。同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。


网上搜集相关图片1

blob.png

网上搜集的排序算法

def ins_sort(lst):
    """ NO.1 插入排序"""
    count = len(lst)
    for i in range(1, count):
        key = lst[i]
        j = i - 1
        while j >= 0:
            if lst[j] > key:
                lst[j + 1] = lst[j]
                lst[j] = key
                j -= 1
            else:
                break
    return lst
if __name__ == '__main__':
    lst = [4, 1, 3, 2, 16, -9, 10, 14, 8, 7]
    print("NO.1 ==> ", ins_sort(lst))

def shell_sort(lst):
    """ NO.2 希尔排序"""
    step = len(lst) // 2
    while step > 0:
        for i in range(step, len(lst)):
            while i >= step and lst[i - step] > lst[i]:
                lst[i], lst[i - step] = lst[i - step], lst[i]
                i -= step
        step = step // 2
    return lst

if __name__ == '__main__':
    lst = [23, 10, 4, 1]
    print("NO.2 ==> ", shell_sort(lst))

def bubble_sort(x):
    """ No.3 冒泡排序 """
    count = len(x)
    for i in range(0, count):
        for j in range(i+1, count):
            if lst[i] > lst[j]:
                lst[i], lst[j] = lst[j], lst[i]
    return lst

if __name__ == '__main__':
    lst = [9, 3, 5, 8, 2, 7, 1]
    print("No.3 ==> ", bubble_sort(lst))

def quick_sort(lst, left, right):
    """ NO.4 快速排序 """
    if left >= right:
        return lst
    key = lst[left]
    low = left
    high = right
    while left < right:
        while left < right and lst[right] >= key:
            right -= 1
        lst[left] = lst[right]
        while left < right and lst[left] <= key:
            left += 1
        lst[right] = lst[left]
    lst[right] = key
    quick_sort(lst, low, left - 1)
    quick_sort(lst, left + 1, high)
    return lst

if __name__ == '__main__':
    lists = [7, 9, 2, 1, 3, -99, 100, 122, 55, 31]
    print("No.4 ==> ", quick_sort(lists, 0, len(lists)-1)) # left起始索引值,right结束索引值,相当于指定范围

def select_sort(lst):
    """ NO.5 选择排序 """
    count = len(lst)
    for i in range(0, count):
        min_record = i
        for j in range(i + 1, count):
            if lst[min_record] > lst[j]:
                min_record = j
        lst[min_record], lst[i] = lst[i], lst[min_record]
    return lst

if __name__ == '__main__':
    lst11 = [7, 9, 2, 1, 3, -99, 100, 122, 55, 31]
    print("NO.5 ==> ", select_sort(lst))

def build_max_heap(to_build_list):
    """建立一个堆"""
    # 自底向上建堆
    for i in range(len(to_build_list)//2 - 1, -1, -1):
        max_heap(to_build_list, len(to_build_list), i)

def max_heap(to_adjust_list, heap_size, index):
    """调整列表中的元素以保证以index为根的堆是一个最大堆"""
    # 将当前结点与其左右子节点比较,将较大的结点与当前结点交换,然后递归地调整子树
    left_child = 2 * index + 1
    right_child = left_child + 1
    if left_child < heap_size and to_adjust_list[left_child] > to_adjust_list[index]:
        largest = left_child
    else:
        largest = index
    if right_child < heap_size and to_adjust_list[right_child] > to_adjust_list[largest]:
        largest = right_child
    if largest != index:
        to_adjust_list[index], to_adjust_list[largest] = \
        to_adjust_list[largest], to_adjust_list[index]
        max_heap(to_adjust_list, heap_size, largest)

def heap_sort(to_sort_list):
    """ NO.6 堆排序"""
    # 先将列表调整为堆
    build_max_heap(to_sort_list)
    heap_size = len(to_sort_list)
    # 调整后列表的第一个元素就是这个列表中最大的元素,将其与最后一个元素交换,然后将剩余的列表再调整为最大堆
    for i in range(len(to_sort_list) - 1, 0, -1):
        to_sort_list[i], to_sort_list[0] = to_sort_list[0], to_sort_list[i]
        heap_size -= 1
        max_heap(to_sort_list, heap_size, 0)

if __name__ == '__main__':
  to_sort_list = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
  heap_sort(to_sort_list)
  print("NO.6 ==> ", to_sort_list)

def merge(left, right):
    i, j = 0, 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

def merge_sort(lists):
    """ NO.7 归并排序 """
    if len(lists) <= 1:
        return lists
    num = len(lists) // 2
    left = merge_sort(lists[:num])
    right = merge_sort(lists[num:])
    return merge(left, right)

if __name__ == '__main__':
    lists = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
    print("NO.7 ==> ", merge_sort(lists))

import math

def radix_sort(lst, radix=10):
    """ NO.8 基数排序"""
    k = int(math.ceil(math.log(max(lst), radix)))
    bucket = [[] for i in range(radix)]
    for i in range(1, k + 1):
        for j in lst:
            bucket[j // (radix**(i - 1)) % (radix ** i)].append(j)
        del lst[:]
        for z in bucket:
            lst += z
            del z[:]
    return lst

if __name__ == '__main__':
    lst = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
    print("NO.8 ==> ", radix_sort(lst))

未经允许不得转载:天府数据港官方信息博客 » [Learn.Practice.Discovery]Vol.2 烧脑不停,折腾不止 时间复杂度&空间复杂度&几种排序算法的Python实现

客官点个赞呗! (0)
分享到:

评论 抢沙发

评论前必须登录!

天府云博 - 做有态度的开发&运维&设计学习分享平台!

联系我们百度云主机