python实现常见的排序算法

一、冒泡排序

def bubble_sort(arr):
    """
    冒泡排序：稳定排序，最差和平均时间复杂度O(n^2)，最优情况是O(n)，即原数组是已排好序的情况，空间复杂度O(1)，即交换 *** 作时使用的临时空间
    实现：比较相邻元素，将较小的放在前面，重复执行，直到所有元素满足正序。
    """
    n = len(arr)
    for i in range(0, n):  # 表示排序的轮次
        is_swap = False  # 表示是否在该轮次有交换 *** 作
        for j in range(1, n-i):
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
                is_swap = True
        if not is_swap:  # 若是该轮次没有交换操作，说明所有元素已经排好序了
            break
    return arr

二、插入排序

def insertion_sort(arr):
    """
    插入排序：稳定排序，最差和平均时间复杂度O(n^2)，最优是O(n)，空间复杂度O(1)，
    实现：将数组分成已排好序和未排序两部分，初始时，首个元素分到已排序，剩余分到未排序部分，然后遍历未排序元素，将其与已排数元素比较，插入到适当的位置
    """
    n = len(arr)
    for i in range(1, n):
        tmp = arr[i]   # 将当前要比较的未排序元素存到临时变量tmp，方便后移
        j = i - 1
        while j >= 0 and arr[j] > tmp:   # 从后往前遍历已排序元素，若是大于当tmp，就往后移一位，否则，就将tmp插到该元素后面
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = tmp 
    return arr 

三、归并排序

3.1 递归方法

def merge(arr, tmp, left, mid, right):
    k = 0 
    i = left
    j = mid + 1 
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            tmp[k] = arr[i]; i += 1
        else:
            tmp[k] = arr[j]; j += 1
        k += 1
    while i <= mid:
        tmp[k] = arr[i]; i += 1; k += 1
    while j <= right:
        tmp[k] = arr[j]; j += 1; k += 1
    arr[left: right+1] = tmp[0: k]
def divide(arr, tmp, left, right):
    if left < right:
        mid = (left+right) // 2
        divide(arr, tmp, left, mid)
        divide(arr, tmp, mid+1, right)
        merge(arr, tmp, left, mid, right)
def merge_sort(arr):
    """
    归并排序：稳定排序，最差和平均和最差时间复杂度O(nlogn)，空间复杂度是O(n)，即tmp和左右边界指针的空间
    实现：递归方法，先将数组递归地对半分组，直到每组仅有一个元素时，两两之间回溯归并，归并操作是将两个已排序的数组合并为一个排序的数组
    """
    n = len(arr)
    left, right = 0, n-1
    tmp = [0] * n
    divide(arr, tmp, left, right)
    return arr

3.2 栈方法