用Python实现常见的排序算法，包括插入法、选择法、快速、冒泡、归并等算法

"""
作者：皮蛋编程(https://www.pidancode.com)
创建日期：2022/3/19
修改日期：2022/3/19
功能描述：用Python实现常见的排序算法
"""

import random
from copy import copy


def directInsertSort(seq):
    """ 直接插入排序 """
    size = len(seq)
    for i in range(1, size):
        tmp, j = seq[i], i
        while j > 0 and tmp < seq[j - 1]:
            seq[j], j = seq[j - 1], j - 1
        seq[j] = tmp
    return seq


def directSelectSort(seq):
    """ 直接选择排序 """
    size = len(seq)
    for i in range(0, size - 1):
        k = i;
        j = i + 1
        while j < size:
            if seq[j] < seq[k]:
                k = j
            j += 1
        seq[i], seq[k] = seq[k], seq[i]
    return seq


def bubbleSort(seq):
    """冒泡排序"""
    size = len(seq)
    for i in range(1, size):
        for j in range(0, size - i):
            if seq[j + 1] < seq[j]:
                seq[j + 1], seq[j] = seq[j], seq[j + 1]
    return seq


def _divide(seq, low, high):
    """快速排序划分函数"""
    tmp = seq[low]
    while low != high:
        while low < high and seq[high] >= tmp: high -= 1
        if low < high:
            seq[low] = seq[high]
            low += 1
        while low < high and seq[low] <= tmp: low += 1
        if low < high:
            seq[high] = seq[low]
            high -= 1
    seq[low] = tmp
    return low


def _quickSort(seq, low, high):
    """快速排序辅助函数"""
    if low >= high: return
    mid = _divide(seq, low, high)
    _quickSort(seq, low, mid - 1)
    _quickSort(seq, mid + 1, high)


def quickSort(seq):
    """快速排序包裹函数"""
    size = len(seq)
    _quickSort(seq, 0, size - 1)
    return seq


def merge(seq, left, mid, right):
    """归并排序"""
    tmp = []
    i, j = left, mid
    while i < mid and j <= right:
        if seq[i] < seq[j]:
            tmp.append(seq[i])
            i += 1
        else:
            tmp.append(seq[j])
            j += 1
    if i < mid: tmp.extend(seq[i:])
    if j <= right: tmp.extend(seq[j:])
    seq[left:right + 1] = tmp[0:right - left + 1]


def _mergeSort(seq, left, right):
    if left == right:
        return
    else:
        mid = int((left + right) / 2)
        _mergeSort(seq, left, mid)
        _mergeSort(seq, mid + 1, right)
        merge(seq, left, mid + 1, right)


# 二路并归排序
def mergeSort(seq):
    size = len(seq)
    _mergeSort(seq, 0, size - 1)
    return seq


if __name__ == '__main__':
    s = [random.randint(0, 100) for i in range(0, 20)]
    print(s)
    print("\n")
    print(directSelectSort(copy(s)))
    print(directInsertSort(copy(s)))
    print(bubbleSort(copy(s)))
    print(quickSort(copy(s)))
    print(mergeSort(copy(s)))

[18, 49, 20, 47, 19, 88, 92, 80, 12, 33, 87, 28, 65, 25, 11, 9, 56, 54, 89, 78]


[9, 11, 12, 18, 19, 20, 25, 28, 33, 47, 49, 54, 56, 65, 78, 80, 87, 88, 89, 92]
[9, 11, 12, 18, 19, 20, 25, 28, 33, 47, 49, 54, 56, 65, 78, 80, 87, 88, 89, 92]
[9, 11, 12, 18, 19, 20, 25, 28, 33, 47, 49, 54, 56, 65, 78, 80, 87, 88, 89, 92]
[9, 11, 12, 18, 19, 20, 25, 28, 33, 47, 49, 54, 56, 65, 78, 80, 87, 88, 89, 92]
[9, 11, 12, 18, 19, 20, 25, 28, 33, 47, 49, 54, 56, 65, 78, 80, 87, 88, 89, 92]