学个排序~

2019-09-07

前言

该补充的算法基础还是要补TuT

快排(Quick Sort)

思路总结:

以某个位置为轴,大于轴的数都移动至右侧,小于轴的数都移动到左侧,轴左右侧的新列表递归选取轴和按大小排列

复杂度:

平均:O(nlogn); 最差:O(n^2)

代码:

def quick_sort(A):
    quick_sort2(A, 0, len(A)-1)

def quick_sort2(A, low, hi):
    # 递归方法
    if hi > low:
        p = partition(A, low, hi)
        quick_sort2(A, low, p-1)
        quick_sort2(A, p+1, hi)

def partition(A, low, hi):
    # 获取轴
    # [轴, 小于轴, 小于轴, 小于轴, 大于轴, 大于轴, 大于轴, 大于轴]
    # [小于轴, 小于轴, 小于轴, 轴, 大于轴, 大于轴, 大于轴, 大于轴]
    # 返回轴
    privot = get_privot(A, low, hi)
    privot_value = A[privot]
    A[low], A[privot] = privot_value, A[low]
    border = low
    for i in range(low+1, hi+1):
        if A[i] < privot_value:
            border += 1
            A[i], A[border] = A[border], A[i]

    A[low], A[border] = A[border], A[low]
    return border

def get_privot(A, low, hi):
    # 选取一个位置为轴
    # 若不选取中间值为轴 最差O(n^2)
    mid = (hi + low) // 2
    s = sorted([A[hi], A[low], A[mid]])
    if s[1] == A[hi]:
        return hi
    elif s[1] == A[low]:
        return low
    else:
        return mid

插入排序(Insertion Sort)

思路:

从左往右,拿起一个数,向左侧找它应该插入的位置

复杂度:

O(n^2)

代码:

def insert_sort(A):
    n = len(A)
    for i in range(1, n):
        # 拿起一个元素
        cur_val = A[i]
        k = 0
        # 比它大的都往右挪一格
        for j in range(i-1, -2, -1):
            k = j
            if cur_val < A[j]:
                A[j+1] = A[j]
            else:
                break
        # 挪出来空的一格把该元素放入
        A[k+1] = cur_val

选择排序(Selection Sort)

思路:

从左往右,找最小值放到最左边

复杂度:

O(n^2)

代码:

def select_sort(A):
    n = len(A)
    for i in range(0, n):
        # 找出A[i:end]中的最小值
        min_idx = i
        for j in range(i+1, n):
            if A[j] < A[min_idx]:
                min_idx = j
        # 将这个最小值交换值A[i]的位置
        if min_idx != i:
            A[min_idx], A[i] = A[i], A[min_idx]

冒泡排序(Bubble Sort)

思路:

从左往右,左侧比右侧大,则交换;一直交换至最右侧,依次排出:第n位为0至n的最大值,第n-1位为0至n-1的最大值

复杂度:

O(n^2)

代码:

def bubble_sort(A):
    n = len(A)
    for i in range(n):
        for j in range(0, n-i-1):
            if A[j] > A[j+1]:
                A[j], A[j+1] = A[j+1], A[j]

归并排序(Merge Sort)

思路:

将列表分为两份,分别对左侧和右侧进行归并排序,排序完之后比较左侧和右侧第一个的大小,小的先放进结果中,再取下一个较小的放入结果,直至取完所有结果

复杂度:

O(nlogn)

代码:

def merge_sort(A):
    merge_sort2(A, 0, len(A)-1)

def merge_sort2(A, first, last):
    if last > first:
        # 拆分为左右两组 分别归并排序
        mid = (first+last) // 2
        merge_sort2(A, first, mid)
        merge_sort2(A, mid+1, last)
        # 合并左右结果
        merge(A, first, mid, last)


def merge(A, first, mid, last):
    left = A[first:mid+1]
    right = A[mid+1:last+1]
    left.append(9999999999)
    right.append(9999999999)
    i = j = 0
    # 依次取左右较小的作为第A[k]值,直至拼接成完整的A[first:last+1]
    for k in range(first, last+1):
        if left[i] <= right[j]:
            A[k] = left[i]
            i += 1
        else:
            A[k] = right[j]
            j += 1