常用算法及其Python实现

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 常用算法及其Python实现

点击上方”python宝典”,关注获取python全套视频,

技术文章第一时间送达!

冒泡排序

常用算法及其Python实现

def bubble_sort(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]

============冒泡排序(优化)============
def bubble_sort_1(li):
    for i in range(len(li)-1): # i表示第几趟
        exchange = False
        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]
                exchange = True
        if not exchange:
            return

选择排序

常用算法及其Python实现

def select(li):
    for i in range(len(li)):
        # 第i趟开始时 无序区:li[i:]
        # 找无序区最小值,保存最小值的位置
        min_index = i
        for j in range(i + 1, len(li)):
            if li[j]  li[min_index]:
                min_index = j
        li[min_index], li[i] = li[i], li[min_index]

插入排序

常用算法及其Python实现

def insert_sort(li):
    for i in range(1, len(li)): # i是摸到的牌的下标
        tmp = li[i]     # tmp是摸到牌的值
        # 方法一
        j = i - 1 # j是手里最后一张牌的下标    li[j]是手里最后一张牌的值
        while j = 0 and li[j]  tmp:   # 两个终止条件:j小于0表示tmp是最小的 顺序不要乱 
            li[j+1] = li[j]
            j -= 1
        # 方法二
        # for j in range(i-1, -1, -1):
        #     if li[j]  tmp:
        #         li[j+1] = li[j]
        #     else:
        #         break
        li[j+1] = tmp   #将摸到的牌 插入到 往前挪过之后的 j 的后一位

快速排序

常用算法及其Python实现

def part(li, left, right):  # 列表,最左索引,最右索引
    tmp = li[left]  # 先找个临时变量把第一个元素存起来
    while left  right:  # 当最左小于最右
        while left  right and li[right] = tmp:  # 当最左最右 且 最右边的值大于等于临时变量
            right -= 1  # 最右 往左 挪 1 个单位长度
        li[left] = li[right]  # 都不满足:把挪完之后的最右的值 赋值给 最左的值(即最右的值小于临时变量时,这个值挪到当前最左的值)
        while left  right and li[left] = tmp:  # 当最左最右 且 最左边的值小于等于临时变量
            left += 1  # 最左 往右 挪 1 个单位长度
        li[right] = li[left]  # 都不满足:把挪完之后的最左的值 赋值给 最右的值(即最左的值大于临时变量时,这个值挪到当前最右的值)
    li[left] = tmp  # 当前最左最右的值相等时,把这个值赋给临时变量
    return left  # 返回当前临时变量的索引


def quick(li, left, right):
    if left  right:  # 如果左索引右索引
        mid = part(li, left, right)  # 调用part进行分区 返回一个索引赋给mid
        quick(li, left, mid - 1)  # 递归调用quick 直到left=mid-1
        quick(li, mid + 1, right)  # 递归调用quick 直到mid+1=right


li = list(range(1000))
import random
random.shuffle(li)
print(li)

quick(li, 0, len(li) - 1)
print(li)

堆排序

常用算法及其Python实现

def sift(li, low, high):
    tmp = li[low]
    i = low
    j = 2 * i + 1
    while j = high: # 退出条件2:当前i位置是叶子结点,j位置超过了high
        # j 指向更大的孩子
        if j + 1 = high and li[j+1]  li[j]:
            j = j + 1 # 如果右孩子存在并且更大,j指向右孩子
        if tmp  li[j]:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:       # 退出条件1:tmp的值大于两个孩子的值
            break
    li[i] = tmp

@cal_time
def heap_sort(li):
    # 1. 建堆
    n = len(li)
    for i in range(n//2-1, -1, -1):
        # i 是建堆时要调整的子树的根的下标
        sift(li, i, n-1)
    # 2.挨个出数
    for i in range(n-1, -1, -1): #i表示当前的high值 也表示棋子的位置
        li[i], li[0] = li[0], li[i]
        # 现在堆的范围 0~i-1
        sift(li, 0, i-1)

归并排序

常用算法及其Python实现

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:
            ltmp.append(li[j])
            j += 1
    while i = mid:
        ltmp.append(li[i])
        i += 1
    while j = high:
        ltmp.append(li[j])
        j += 1
    # for k in range(low, high+1):
    #     li[k] = ltmp[k-low]
    li[low:high+1] = ltmp

def merge_sort(li, low, high):
    if low  high:
        mid = (low + high) // 2
        merge_sort(li, low, mid)
        merge_sort(li, mid+1, high)
        merge(li, low, mid, high)

# li = list(range(10000))
# random.shuffle(li)
# merge_sort(li, 0, len(li)-1)
# print(li)
li = [10,4,6,3,8,2,5,7]
merge_sort(li, 0, len(li)-1)

总结

常用算法及其Python实现 常用算法及其Python实现

识别图中二维码,欢迎关注python宝典

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 常用算法及其Python实现


 上一篇
python之WebSocket协议 python之WebSocket协议
点击上方”python宝典”,关注获取python全套视频, 技术文章第一时间送达! 一、WebSocket理论部分1、websocket是什么 Websocket是html5提出的一个协议规范,参考rfc6455。 websocket约定
2021-04-05
下一篇 
算法基础 算法基础
点击上方”python宝典”,关注获取python全套视频, 技术文章第一时间送达! 一、什么是算法?算法(Algorithm):一个计算过程,解决问题的方法 一个算法应该具有以下七个重要的特征: ①有穷性(Finitene
2021-04-05