Python實現排序算法2

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]