温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Python实现排序算法2

发布时间:2020-05-19 10:13:27 来源:网络 阅读:203 作者:小嘉欣 栏目:编程语言

4.希尔排序

# -*- coding:utf-8 -*-
def shell_sort(alist):
    """希尔排序"""
    n = len(alist)
    gap = n // 2

    while gap >= 1:
        for j in range(gap,n):
            i = j
            while i > 0:
                if alist[i] < alist[i-gap]:
                    alist[i],alist[i-gap] = alist[i-gap],alist[i]
                    i -=gap
                else:
                    break
        gap //= 2

if __name__ == "__main__":
    a = [6,86,3,5,0,43,90,100]
    print(a)
    shell_sort(a)
    print(a)

# [6, 86, 3, 5, 0, 43, 90, 100]
# [0, 3, 5, 6, 43, 86, 90, 100]

5.快速排序

# -*- coding:utf-8 -*-
def quick_sort(alist,first,last):
    """快速排序"""
    if first >= last:
        return
    # n = len(alist)
    mid_value = alist[first]
    low = first
    high = last

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

        # Low右移
        while low <high and alist[low] < mid_value:
            low += 1
        alist[high]=alist[low]

    alist[low]=mid_value
    quick_sort(alist,first,low-1)
    quick_sort(alist,low+1, last)

if __name__ == "__main__":
    a = [6,86,3,5,0,43,90,100]
    print(a)
    quick_sort(a,0,len(a)-1)
    print(a)

# [6, 86, 3, 5, 0, 43, 90, 100]
# [0, 3, 5, 6, 43, 86, 90, 100]

6.归并排序

# -*- coding:utf-8 -*-
def merge_sort(alist):
    """归并排序"""
    n = len(alist)
    if n <= 1:
        return alist
    mid =n // 2

    left_alist = merge_sort(alist[:mid])
    right_alist = merge_sort(alist[mid:])

    left_pointer,right_pointer = 0,0
    result = []

    while left_pointer < len(left_alist) and right_pointer < len(right_alist):
        if left_alist[left_pointer] < right_alist[right_pointer]:
            result.append(left_alist[left_pointer])
            left_pointer += 1
        else:
            result.append(right_alist[right_pointer])
            right_pointer += 1
    result += left_alist[left_pointer:]
    result += right_alist[right_pointer:]
    return  result

if __name__ == "__main__":
    a = [6, 86, 3, 5, 0, 43, 90, 10]
    print(a)
    sorted_list = merge_sort(a)
    print(sorted_list)

# [6, 86, 3, 5, 0, 43, 90, 10]
# [0, 3, 5, 6, 10, 43, 86, 90]
向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI