数据结构学习-python实现-数据排序--0412

def mergesort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergesort(lefthalf)  # 递归过程
        mergesort(righthalf)

        i = j = k = 0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:  # 分裂后选择较小的值，放入临时列表
                alist[k] = lefthalf[i]
                i += 1
            else:
                alist[k] = righthalf[j]
                j += 1
            k += 1

        while i < len(lefthalf):  # 左侧一半的长度大于右侧，需单独进行合并步骤
            alist[k] = lefthalf[i]
            i += 1
            k += 1

        while j < len(righthalf):
            alist[k] = righthalf[j]
            j += 1
            k += 1
    print('Merging', alist)

mergesort([9, 8, 7, 6, 5, 4, 3, 2, 1])

def merge_sort(lst):
    if len(lst) <= 1:
        return lst
    middle = len(lst) // 2
    left = merge_sort(lst[:middle])
    right = merge_sort(lst[middle:])

    merged = []
    while left and right:
        if left[0] <= right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))

    merged.extend(right if right else left)  # 在尾部添加多出部分
    return merged

print(merge_sort([9, 8, 7, 6, 5, 4, 3, 2]))
# 时间复杂度O(logn)
# 归并过程复杂度为O(n)
# 综合考虑O(nlogn)

def quick_sort(alist):
    quick_sort_helper(alist, 0, len(alist)-1)

def quick_sort_helper(alist, first, last):
    if first < last:
        split_point = partition(alist, first, last)
        quick_sort_helper(alist, first, split_point-1)  # 递归
        quick_sort_helper(alist, split_point+1, last)

def partition(alist, first, last):
    pivotvalue = alist[first]  # 定义中位值，假设第一个值既是中位值
    leftmark = first + 1  # 左侧值从第二个值开始比较
    rightmark = last  # 右侧值从最后一个开始比较

    done = False
    while not done:
        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark += 1  # 判断左侧值小于中位值
        while rightmark >= leftmark and alist[rightmark] >= pivotvalue:
            rightmark -= 1
        if rightmark < leftmark:
            done = True
        else:
            alist[leftmark], alist[rightmark] = alist[rightmark], alist[leftmark]

    alist[first], alist[rightmark] = alist[rightmark], alist[first]
    return rightmark

alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quicksort(alist)
print(alist)
# 分裂复杂度O(logn)
# 中值选取的可能会是O(n²)