对插入排序、选择排序、冒泡（双向冒泡）、堆排序、快速排序、归并排序等多种排序算法进行实现，输出排序中间过程、统计关键字的比较次数和记录的移动次数代码

好的，以下是这些排序算法的实现代码，包括排序过程中的比较次数和记录移动次数。

1. 插入排序

def insertion_sort(arr):
    n = len(arr)
    cmp_count = 0
    mov_count = 0
    for i in range(1, n):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
            cmp_count += 1
            arr[j+1] = arr[j]
            mov_count += 1
            j -= 1
        arr[j+1] = key
        mov_count += 1
    return arr, cmp_count, mov_count

2. 选择排序

def selection_sort(arr):
    n = len(arr)
    cmp_count = 0
    mov_count = 0
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            cmp_count += 1
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        mov_count += 3
    return arr, cmp_count, mov_count

3. 冒泡排序

def bubble_sort(arr):
    n = len(arr)
    cmp_count = 0
    mov_count = 0
    for i in range(n):
        for j in range(n-i-1):
            cmp_count += 1
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                mov_count += 3
    return arr, cmp_count, mov_count

4. 堆排序

def heap_sort(arr):
    def heapify(arr, n, i):
        nonlocal cmp_count, mov_count
        largest = i
        l = 2*i + 1
        r = 2*i + 2
        if l < n and arr[largest] < arr[l]:
            cmp_count += 1
            largest = l
        if r < n and arr[largest] < arr[r]:
            cmp_count += 1
            largest = r
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            mov_count += 3
            heapify(arr, n, largest)

    n = len(arr)
    cmp_count = 0
    mov_count = 0
    for i in range(n//2-1, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        mov_count += 3
        heapify(arr, i, 0)
    return arr, cmp_count, mov_count

5. 快速排序

def quick_sort(arr):
    def partition(arr, low, high):
        nonlocal cmp_count, mov_count
        i = low - 1
        pivot = arr[high]
        for j in range(low, high):
            cmp_count += 1
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
                mov_count += 3
        arr[i+1], arr[high] = arr[high], arr[i+1]
        mov_count += 3
        return i+1

    def quicksort(arr, low, high):
        if low < high:
            pi = partition(arr, low, high)
            quicksort(arr, low, pi-1)
            quicksort(arr, pi+1, high)

    n = len(arr)
    cmp_count = 0
    mov_count = 0
    quicksort(arr, 0, n-1)
    return arr, cmp_count, mov_count

6. 归并排序

def merge_sort(arr):
    def merge(arr, l, m, r):
        nonlocal cmp_count, mov_count
        L = arr[l:m+1]
        R = arr[m+1:r+1]
        i = j = 0
        k = l
        while i < len(L) and j < len(R):
            cmp_count += 1
            if L[i] <= R[j]:
                arr[k] = L[i]
                mov_count += 1
                i += 1
            else:
                arr[k] = R[j]
                mov_count += 1
                j += 1
            k += 1
        while i < len(L):
            arr[k] = L[i]
            mov_count += 1
            i += 1
            k += 1
        while j < len(R):
            arr[k] = R[j]
            mov_count += 1
            j += 1
            k += 1

    def mergesort(arr, l, r):
        if l < r:
            m = (l+r) // 2
            mergesort(arr, l, m)
            mergesort(arr, m+1, r)
            merge(arr, l, m, r)

    n = len(arr)
    cmp_count = 0
    mov_count = 0
    mergesort(arr, 0, n-1)
    return arr, cmp_count, mov_count