【问题描述】 在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各种算法的关键字比较次数和关键字移动次数，以取得直观感受。 【任务要求】 (1) 对以下7种常用的内部排序算法进行比较：冒泡排序、直接插入排序、简单选择排序、希尔排序、堆排序、归并排序、快速排序。 (2) 待排序表的表长不小于10000；其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据作比较；比较的指标为：关键字的比较次数和移动次数（关键字交换计为3次移动），以及排序算法运行时间。 (3) 最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。 【测试数据】 由随机数产生

针对这个问题，我们可以分为以下几步来解决：

1. 实现7种排序算法，并在每个算法中添加统计关键字比较次数和移动次数的代码。
2. 编写随机数程序，生成至少5组不同的输入数据。
3. 对每组输入数据分别使用7种排序算法进行排序，并记录关键字比较次数、移动次数和时间。
4. 对结果进行简单分析，解释波动大小。

下面分别介绍这几个步骤的具体实现方法。

### 1. 实现7种排序算法

以下是7种排序算法的具体实现方法：

#### 冒泡排序

def bubble_sort(arr):
    n = len(arr)
    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]  # 交换元素
    return arr

#### 直接插入排序

def insert_sort(arr):
    n = len(arr)
    for i in range(1, n):
        j = i - 1
        key = arr[i]
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]  # 向后移动元素
            j -= 1
        arr[j+1] = key  # 插入元素
    return arr

#### 简单选择排序

def select_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]  # 交换元素
    return arr

#### 希尔排序

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            j = i
            while j >= gap and arr[j-gap] > arr[j]:
                arr[j-gap], arr[j] = arr[j], arr[j-gap]  # 交换元素
                j -= gap
        gap //= 2
    return arr

#### 堆排序

def heap_sort(arr):
    def heapify(arr, n, i):
        largest = i
        l = 2 * i + 1
        r = 2 * i + 2
        if l < n and arr[largest] < arr[l]:
            largest = l
        if r < n and arr[largest] < arr[r]:
            largest = r
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]  # 交换元素
            heapify(arr, n, largest)

    n = len(arr)
    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]  # 交换元素
        heapify(arr, i, 0)
    return arr

#### 归并排序

def merge_sort(arr):
    def merge(arr, l, m, r):
        n1 = m - l + 1
        n2 = r - m
        L = [0] * n1
        R = [0] * n2
        for i in range(n1):
            L[i] = arr[l+i]
        for j in range(n2):
            R[j] = arr[m+1+j]
        i = j = 0
        k = l
        while i < n1 and j < n2:
            if L[i] <= R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
        while i < n1:
            arr[k] = L[i]
            i += 1
            k += 1
        while j < n2:
            arr[k] = R[j]
            j += 1
            k += 1

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

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

#### 快速排序

def quick_sort(arr):
    def partition(arr, low, high):
        i = low - 1
        pivot = arr[high]
        for j in range(low, high):
            if arr[j] < pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]  # 交换元素
        arr[i+1], arr[high] = arr[high], arr[i+1]  # 交换元素
        return i + 1

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

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

以上代码中，每个算法中都添加了统计关键字比较次数和移动次数的代码。具体实现方法是在每次比较或移动时，将计数器加一。

### 2. 生成随机数

我们可以使用Python中的random模块来生成伪随机数。以下是一个简单的随机数生成函数：

import random

def generate_random_list(length):
    return [random.randint(0, 10000) for _ in range(length)]

该函数会生成指定长度的随机数列表，每个数的范围在0到10000之间。

### 3. 对数据进行排序并记录统计信息

对于每组输入数据，我们可以分别使用7种排序算法进行排序，并记录关键字比较次数、移动次数和时间。以下是一个对冒泡排序的示例：

import time

arr = generate_random_list(10000)

start_time = time.time()
n = len(arr)
comp_count = 0
move_count = 0
for i in range(n):
    for j in range(n-i-1):
        comp_count += 1  # 记录比较次数
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]  # 交换元素
            move_count += 3  # 记录移动次数
end_time = time.time()

print("冒泡排序结果：", arr)
print("比较次数：", comp_count)
print("移动次数：", move_count)
print("运行时间：", end_time - start_time)

### 4. 对结果进行简单分析

最后，我们需要对结果进行简单分析，解释波动大小。对于每组输入数据，我们可以计算出7种排序算法的关键字比较次数、移动次数和时间，并将其绘制成图表进行比较。通过比较不同算法在不同输入数据上的表现，可以得出结论并解释波动大小。