Python数据结构04-冒泡、选择、插入、归并、希尔、快速排序、二分查找

2283-鲁同学

发表文章数:32

首页 » Python » 正文

各种排序实现

排序思想不做描述。

#冒泡
def bubble_sort(alist):
    for x in range(0,len(alist)-1):
        isswap = False
        for y in range(x,len(alist)):
            # print(x,y)
            if alist[x] > alist[y]:
                isswap = True
                alist[x] , alist[y] = alist[y] , alist[x]
        if not isswap:
            break
#选择
def selection_sort(alist):
    for x in range(len(alist)):
        minindex = x
        for y in range(x,len(alist)):
            if alist[y]<alist[minindex]:
                minindex = y
        alist[x],alist[minindex] = alist[minindex],alist[x]

#插入
def insert_sort(alist):
    for x in range(1,len(alist)):# 从第二个位置,即下标为1的元素开始向前插入
        for y in range(x,0,-1):
            if alist[y] < alist[y-1]:
                alist[y],alist[y-1] = alist[y-1],alist[y]

#快速
def quick_sort(alist, start, end):
    if start >= end:
        return
    mid = alist[start]
    # print(start,end,mid)
    l = start
    r = end
    while l<r:
        while l<r and alist[r]>mid:
            r-=1
        alist[l] = alist[r]
        while l<r and alist[l]<mid:
            l+=1
        alist[r] = alist[l]
    alist[l] = mid
    quick_sort(alist,start,l-1)
    quick_sort(alist,l+1,end)

#希尔
def shell_sort(alist):
    n = len(alist)
    gap = n//2
    while gap>0:
        for i in range(gap,n):
            temp = alist[i]
            j = i
            while j>=gap and alist[j-gap]>temp:
                alist[j] = alist[j-gap]
                j-=gap
            alist[j]=temp
        gap = gap//2
# 归并
def merge_sort(alist):
    "返回更新完成的新的有序列表"
    if len(alist)<=1:
        return alist
    num = len(alist)//2
    left = merge_sort(alist[:num])
    # print(left)
    right = merge_sort(alist[num:])
    # print(right)
    return merge(left,right)
def merge(left, right):
    "返回有序数组"
    l,r = 0,0
    nums = []
    while l<len(left) and r<len(right):
        if left[l]>right[r]:
            nums.append(right[r])
            r+=1
        else:
            nums.append(left[l])
            l+=1
    while l<len(left):
        nums.append(left[l])
        l+=1
    while r<len(right):
        nums.append(right[r])
        r+=1
    return nums

if __name__ == "__main__":
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    # insert_sort(alist)
    alist = merge_sort(alist)
    print(alist)

常见排序算法效率比较

Python数据结构04-冒泡、选择、插入、归并、希尔、快速排序、二分查找

搜索

常见搜索方式
顺序查找、二分法查找、二叉树查找、哈希查找

二分法查找

对于有序数组Ologn

def binary_search(alist, item):
      first = 0
      last = len(alist)-1
      while first<=last:
          midpoint = (first + last)/2
          if alist[midpoint] == item:
              return True
          elif item < alist[midpoint]:
              last = midpoint-1
          else:
              first = midpoint+1
    return False
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))

未经允许不得转载:作者:2283-鲁同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《Python数据结构04-冒泡、选择、插入、归并、希尔、快速排序、二分查找》 发布于2021-10-25

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录