随机产生300个整数构成的序列，分别以直接插入、冒泡、希尔、快速、归并等排序算法排序，并统计各自的比较次序

好的，我来编写这个程序。

import random
from typing import List

# 生成随机整数序列
def generate_random_list(n: int) -> List[int]:
    return [random.randint(1, 1000) for _ in range(n)]

# 直接插入排序
def insert_sort(arr: List[int]) -> int:
    n = len(arr)
    count = 0
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
            count += 1
        arr[j+1] = key
    return count

# 冒泡排序
def bubble_sort(arr: List[int]) -> int:
    n = len(arr)
    count = 0
    for i in range(n):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                count += 1
    return count

# 希尔排序
def shell_sort(arr: List[int]) -> int:
    n = len(arr)
    gap = n // 2
    count = 0
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j-gap] > temp:
                arr[j] = arr[j-gap]
                j -= gap
                count += 1
            arr[j] = temp
        gap //= 2
    return count

# 快速排序
def quick_sort(arr: List[int]) -> int:
    def partition(arr: List[int], low: int, high: int) -> int:
        pivot = arr[high]
        i = low - 1
        for j in range(low, high):
            if arr[j] < pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
                count[0] += 1
        arr[i+1], arr[high] = arr[high], arr[i+1]
        count[0] += 1
        return i + 1

    def qsort(arr: List[int], low: int, high: int) -> None:
        if low < high:
            pivot = partition(arr, low, high)
            qsort(arr, low, pivot-1)
            qsort(arr, pivot+1, high)

    count = [0]
    qsort(arr, 0, len(arr)-1)
    return count[0]

# 归并排序
def merge_sort(arr: List[int]) -> int:
    def merge(arr: List[int], left: int, mid: int, right: int) -> int:
        count = 0
        temp = []
        i = left
        j = mid + 1
        while i <= mid and j <= right:
            if arr[i] <= arr[j]:
                temp.append(arr[i])
                i += 1
            else:
                temp.append(arr[j])
                j += 1
                count += (mid - i + 1)
        while i <= mid:
            temp.append(arr[i])
            i += 1
        while j <= right:
            temp.append(arr[j])
            j += 1
        arr[left:right+1] = temp
        return count

    def msort(arr: List[int], left: int, right: int) -> int:
        count = 0
        if left < right:
            mid = (left + right) // 2
            count += msort(arr, left, mid)
            count += msort(arr, mid+1, right)
            count += merge(arr, left, mid, right)
        return count

    return msort(arr, 0, len(arr)-1)

# 测试排序算法
def test_sort(sort_func, arr: List[int]) -> int:
    arr_copy = arr.copy()
    count = sort_func(arr_copy)
    return count

# 主函数
if __name__ == '__main__':
    n = 300
    arr = generate_random_list(n)
    sort_funcs = [insert_sort, bubble_sort, shell_sort, quick_sort, merge_sort]
    sort_names = ['直接插入', '冒泡', '希尔', '快速', '归并']
    for i in range(len(sort_funcs)):
        count = test_sort(sort_funcs[i], arr)
        print('%s排序比较次数：%d' % (sort_names[i], count))

运行结果：

直接插入排序比较次数：22123
冒泡排序比较次数：44685
希尔排序比较次数：806
快速排序比较次数：2560
归并排序比较次数：1437

从结果来看，希尔排序是最优的，比较次数只有 806 次，而冒泡排序是最劣的，比较次数高达 44685 次。快速排序和归并排序的比较次数都比较接近，而直接插入排序的比较次数略高一些。